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.

- Supplementary Exercises not yet in text (to be added in the third edition)
- Solution manual - available to
**instructors only**: to get the solution manual, go to www.prenhall.com, search for this book by title or ISBN, click on "instructor" on the page for the book, fill out the requested information identifying you as an instructor, and wait for email with instructions for accessing the solution manual. - 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.

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)*" -

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.

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.