Written by one of the leading authors in the field, this text provides a student-friendly approach to graph theory for undergraduates. Much care has been given to present the material at the most effective level for students taking a first course in graph theory. Gary Chartrand and Ping Zhang's lively and engaging style, historical emphasis, unique examples and clearly-written proof techniques make it a sound yet accessible text that stimulates interest in an evolving subject and exploration in its many applications.
This text is part of the Walter Rudin Student Series in Advanced Mathematics.
1 Introduction
1.1 Graphs and Graph Models
1.2 Connected Graphs
1.3 Common Classes of Graphs
1.4 Multigraphs and Digraphs
2 Degrees
2.1 The Degree of a Vertex
2.2 Regular Graphs
2.3 Degree Sequences
2.4 Excursion: Graphs and Matrices
2.5 Exploration: Irregular Graphs
3 Isomorphic Graphs
3.1 The Definition of Isomorphism
3.2 Isomorphism as a Relation
3.3 Excursion: Graphs and Groups
3.4 Excursion: Reconstruction and Solvability
4 Trees
4.1 Bridges
4.2 Trees
4.3 The Minimum Spanning Tree Problem
4.4 Excursion: The Number of Spanning Trees
5 Connectivity
5.1 Cut-Vertices
5.2 Blocks
5.3 Connectivity
5.4 Menger's Theorem
5.5 Exploration: Geodetic Sets
6 Traversability
6.1 Eulerian Graphs
6.2 Hamiltonian Graphs
6.3 Exploration: Hamiltonian Walks and Numbers
6.4 Excursion: The Early Books of Graph Theory
7 Digraphs
7.1 Strong Digraphs
7.2 Tournaments
7.3 Excursion: Decision-Making
7.4 Exploration: Wine Bottle Problems
8 Matchings and Factorization
8.1 Matchings
8.2 Factorization
8.3 Decompositions and Graceful Labelings
8.4 Excursion: Instant Insanity
8.5 Excursion: The Petersen Graph
8.6 Exploration: -Labeling of Graphs
9 Planarity
9.1 Planar Graphs
9.2 Embedding Graphs on Surfaces
9.3 Excursion: Graph Minors
9.4 Exploration: Embedding Graphs in Graphs
10 Coloring
10.1 The Four Color Problem
10.2 Vertex Coloring
10.3 Edge Coloring
10.4 Excursion: The Heawood Map Coloring Theorem
10.5 Exploration: Local Coloring
11 Ramsey Numbers
11.1 The Ramsey Number of Graphs
11.2 Turan's Theorem
11.3 Exploration: Rainbow Ramsey Numbers
11.4 Excursion: Erdös Numbers
12 Distance
12.1 The Center of a Graph
12.2 Distant Vertices
12.3 Excursion: Locating Numbers
12.4 Excursion: Detour and Directed Distance
12.5 Exploration: Channel Assignment
12.6 Exploration: Distance Between Graphs
13 Domination
13.1 The Domination Number of a Graph
13.2 Exploration: Stratification
13.3 Exploration: Lights Out
13.4 Excursion: And Still It Grows More Colorful
Appendix 1 Sets and Logic
Appendix 2 Equivalence Relations and Functions
Appendix 3 Methods of Proof
