ISBN 0-471-38925-0. Available from Super Book Deals, Barnes & Noble, and Amazon.com.
From the Preface: Where it can be found at all, an undergraduate course in graph theory is typically listed among the electives for majors in the mathematical sciences. For better or worse, elective courses often find themselves competing with each other for enrollments in today's cafeteria style curriculum. Evolving in such an environment, this book might best be described as an invitation to graph theory. A mathematically rigorous introduction, it is neither an exhaustive overview nor an encyclopedic reference. To borrow a phrase from the early calculus reform movement, it is a lean and lively text, designed to attract and engage. Preference is given to the kinds of things students can, figuratively speaking, get their hands on. The selection is dictated less by intrinsic importance and more by how well a topic lends itself to being pictured, calculated, manipulated, or counted. While applications are numerous, they have been chosen and presented as much to seduce as to inform. In a similar spirit, not because it is central to graph theory, but because it is a useful device, graph coloring is deployed throughout the book as a unifying theme. The idea is to create the impression, not of a series of theorems about graphs, but of a subject that can be presented as a unified theory. The result is a book that goes deeply enough into a sufficiently wide variety of topics to display, not only the flavor of graph theory, but some of its power and elegance as well.
Flexibility: The text was planned to be a versatile instructional tool. Following a basic foundation in Chapters 1-3, an instructor is free to pick and choose the most appropriate topics from four independent strands: Chapters 4-5, Chapter 6, Chapter 10, and/or Chapters 7-9.
Prerequisite: Among the prerequisites for a course based on this book should be the sophomore linear algebra course commonly found among the lower division requirements for majors in the mathematical and physical sciences. Elementary linear algebra is used most heavily in Chapter 9, where the reader is presumed to have been exposed to the definitions of eigenvalue, eigenvector, and the characteristic polynomial of a real [symmetric] matrix. Apart from this general prerequisite, the recipe for counting nonisomorphic graphs, found in the latter part of Chapter 10, supposes the reader to be acquainted with the disjoint cycle factorization of a permutation.
From the marketing blurb: This mathematically rigorous treatment is tempered and enlivened by numerous illustrations, revealing examples, seductive applications, historical references, and a spirited exposition. The rich assortment of well chosen exercises range in difficulty from routine to challenging. Intended to be neither a comprehensive overview nor an encyclopedic reference, this focused introduction to graph theory goes deeply enough into a sufficiently wide variety of topics to demonstrate its flavor, power, elegance, and vitality.
1 Invariants: Definitions; pros and cons of pictures; different vs. nonisomorphic graphs; isomorphism problem, invariants; "first theorem of graph theory"; adjacency matrix.
2 Chromatic Number: Proper colorings; Fundamental Counting Principle; independence, clique, and chromatic numbers; chromatic polynomial; unions and joins; bipartite graphs, trees; paraffins, Wiener and Balaban (chemical) indices.
3 Connectivity: Quantitative measures of connectivity; blocks, k-connectedness; separating sets, internally disjoint paths, Menger's Theorem; Whitney's Broken Cycle Theorem.
4 Planar Graphs: Euler's Formula; Kuratowski's Theorem; Five and Four-Color Theorems; geometric dual; embeddings in orientable surfaces, graph genus; theorems of Heawood and Ringel & Youngs.
5 Hamiltonian Cycles: Necessary conditions; sufficient conditions; closure; Chvatal graphs; hamiltonian plane graphs; theorems of Whitney and Grinberg.
6 Matchings: Kekule and benzene; perfect matchings; matching polynomial; adjacency characteristic polynomial; matching and covering numbers, Egervary-Konig Theorem from Menger's Theorem; theorems of Hall and Tutte.
7 Graphic Sequences: Partitions, graphic partitions, Havel-Hakimi criterion; graphs with the same degree sequence, Ryser switches; majorization, Ferrers diagrams; Ruch-Gutman criterion; threshold partitions and graphs.
8 Chordal Graphs: Weak majorization, shifted shapes, Ruch-Gutman criterion exposed; split partitions and graphs; chordal graphs; perfect graphs; simplicial vertices and chromatic polynomials.
9 Oriented Graphs: Acyclic orientations, Stanley's Theorem; Laplacian matrix, spanning tree number; spectral characterization of certain graph invariants; isospectral and decomposable graphs.
10 Edge Colorings: Ramsey numbers, upper and lower bounds, Erdos's probabilistic technique; Polya-Redfield approach to graph enumeration, cycle index polynomial.
Hints and Answers to selected odd numbered problems.
Bibliography
Index
Index of Notation
Reviewed, e.g., in