Introduction to Graph Theory - Second edition

This is the home page for Introduction to Graph Theory, by Douglas B. West.
Published by Prentice Hall 1996, 2001.
Second edition, xx+588 pages, 1296 exercises, 447 figures, ISBN 0-13-014400-2.
First edition 512+xvi pages, 870 exercises, 312 figures, ISBN 0-13-227828-6.

Resources

Supplementary Exercises not yet in text (to be added in the third edition)
Solution manual - available to instructors only, from the publisher. The publisher is now Pearson. Solution manuals posted for sale on the internet are stolen property; the solution manual is owned by the publisher and is not authorized for sale.
Syllabus for a one-semester beginning course (used at U Illinois) postscript pdf
Contents and Preface for second edition (postscript)
Errata for second edition

Corrections to notation and to other mathematical aspects
Comments and updates (corrections to references, comments on proofs or exercises, etc.)
Minor typos (errors in spelling, punctuation, etc.)

Inductive proof of Matrix Tree Theorem (ps pdf) without Cauchy-Binet Formula
Resources for first edition (no longer maintained): Errata, Syllabus, Contents and Preface.

Reader Poll on Terminology

It is easy to invent terminology in graph theory, but independently invented terminology is unlikely to agree. I solicited votes on five questions of terminology and will try to honor the results in the third edition. Voting has petered out, so am I no longer soliciting additional votes. I leave the vote totals and discussion of the alternatives here for interested readers. I'm still happy to receive comments on points not covered here.

On a separate page is a discussion of the notation for the number of vertices and the number of edges of a graph G, based on feedback from the discrete mathematics community.

Comments on other aspects of terminology are also welcome. However, I do not expect to make any change regarding "cycle" vs. "circuit". "Even graph" is my compromise expression for the condition that all vertex degrees are even, and I will continue to use "cycle" for a 2-regular connected graph, "circuit" for a cyclically-edge-ordered connected even graph, and "circuit" for a minimal dependent set in a matroid.

Vote totals
Question 1: "simple graph"/"graph" - 17.5; "graph"/"multigraph" - 53; "simple graph"/"graph"/"multigraph" - 4; other - 2.
Question 2: "partite sets" - 21; "color classes" - 14.5; "parts" - 9; "classes" or "vertex classes" - 3; "sides" - 5; "blocks" - .5; "shores" - 2; "bipartite classes" - 1.
Question 3: "pairwise internally disjoint paths" - 13; "independent paths" - 31; other - 6 ("internally independent", "vertex-disjoint", etc.).
Question 4: "M-saturated" - 11; "M-covered" - 20.5; other - 2 ("matched").
Question 5: "\chi(G;k)" - 0; "\pi_G(k)" - 0; "P_G(k)" - 1; other - 0.

Question 1: graph, simple graph, multigraph

What is a "graph"? That is, how do we treat loops and multiple edges? I avoided using "multigraph" in the second edition, because many students think a "multigraph" must have multiple edges, and it seemed that the most general object should have the generic name. Thus I used "simple graph" and "graph" rather than "graph" and "multigraph".

This choice may not be best. Most research and applications in graph theory concern graphs without multiple edges or loops, and often multiple edges can be modeled by edge weights. On the other hand, some topics naturally use multiple edges (Eulerian circuits 1.2, spanning tree enumeration 2.2, bipartite matching 3.1, edge-connectivity 4.1, network flow 4.3, acyclic orientations 5.3, embeddings and their duals 6.1-6.3, edge-coloring 7.1, matroids and minors 8.2). Other topics exclude or ignore multiple edges (independence and domination 3.1, connectivity 4.1, vertex coloring 5.1-5.3, maximum triangle-free graphs 5.2, maximal planar graphs and triangulations 6.1, spanning cycles 7.2). It is convenient in research to use "graph" for whichever model is the current context, but this practice does not work well in a beginning course.

If graph theory cannot decide this, consider mathematics more generally. "Graph/multigraph" would be consistent with "set/multiset" in combinatorics. Also, "hypergraph" often refers to a family of sets, without repeated sets. Finally, the "graph of a relation" is a subset of a cartesian product, with no repeated elements. Consistency in mathematics suggests using "graph/multigraph".

There are also pedagogical considerations. Letting "graph" forbid loops and multiple edges simplifies the first notion for students, making it possible to correctly view the edge set as a set of vertex pairs and avoid the technicalities of an incidence relation in the first definition. Beginning students do not need to know which elementary statements extend without change to multigraphs; important instances like the degree-sum formula can be mentioned explicitly. When "graph" forbids loops and multiple edges, using the word "graph" may make a statement less general, but it won't make it incorrect. On the other hand, I have learned by painful example that when "graph" allows loops and multiple edges, there are countless exercises that acquire annoying counterexamples when the word "simple" is omitted.

Question 2: partite sets

The two independent sets in a bipartition of a bipartite graph are fundamental objects in discussion of bipartite graphs. We need a good term for them. "Partite set" is precise but confounds students; they often call the partite sets of a bipartition "partites" or "partitions". Hence this term may impede learning.

In combinatorics, the elements of a partition are often called "blocks", but that word is not available in graph theory. Another common term is "classes", but this seems too general. Graph theorists often use "parts", but this seems too vague and informal for a text. "Color classes" agrees with later usage in coloring, suggests a choice of the bipartition when the graph is disconnected, and extends to multipartite graphs. Unfortunately, "color classes" suggests the outcome of an optimization problem, while a bipartition is often a presupposed structural condition.

The precise terms are awkward, while the terms used when discussing research seem too informal for instruction. Someone must have a good term for this.

Question 3: pairwise internally disjoint paths

This term is precise but causes suffering. It takes students a long time to understand what it means, and using it carefully in lecture is always awkward. What about the term "independent"? A set of x,y-paths is independent if the paths are pairwise internally disjoint. This would parallel the notion of independent set of vertices, which are pairwise non-adjacent. Indeed, independent x,y-paths form an independent set in the intersection graph of the internal vertex sets of x,y-paths. Already we sometimes call a matching an "independent set of edges" for similar reasons.

Question 4: "M-saturated" vs. "M-covered"

We use "M-saturated" to describe a vertex that is an endpoint of an edge in a matching M. This usage is traditional, but some have questioned the need for introducing special terminology for this in graph theory. Would it be better to use a term like "M-covered" that emphasizes the graph-theoretic meaning? To be fair, it should be noted that "M-saturated" means that this feasible solution in the associated linear program "saturates" the corresponding vertex constraint with equality, which becomes a more significant statement in the more general "b-matching" problem. On the other hand, it has been observed that one can guess the meaning of "M-covered" without seeing the definition (unlike "M-saturated"), and "M-covered" makes more sense to non-native speakers of English.

Question 5: notation for chromatic polynomial

Students in a beginning graph theory course sometimes misread the notation \chi(G;k) for chromatic polynomial as meaning chromatic number. Is there a better choice?