Chapter 1 Fundamental Concepts

1.1 What Is a Graph？

The Definition

Graphs as Models

Matrices and Isomorphism

Decomposition and Special Graphs

Exercises

1.2 Paths,Cycles,and Trails

Connection in Graphs

Bipartite Graphs

Eulerian Circuits

Exercises

1.3 Vertex Degrees and Counting

Counting and Bijections

Extremal Problems

Graphic Sequences

Exercises

1.4 Directed Graphs

Definitions and Examples

Vertex Degrees

Eulerian Digraphs

Orientations and Tournaments

Exercises

Chapter 2 Trees and Distance

2.1 Basic Properties

Properties of Trees

Distance in Trees and Graphs

Disjoint Spanning Trees(optional)

Exercises

2.2 Spanning Trees and Enumeration

Enumeration of Trees

Spanning Trees in Graphs

Decomposition and Graceful Labelings

Branchings and Eulerian Digraphs(optional)

Exercises

2.3 Optimization and Trees

Minimum Spanning Tree

Shortest Paths

Trees in Computer Science(optional)

Exercises

Chapter 3 Matchings and Factors

3.1 Matchings and Covers

Maximum Matchings

Hall's Matching Condition

Min-Max Theorems

Independent Sets and Covers

Dominating Sets(optional)

Exercises

3.2 Algorithms and Applications

Maximum Bipartite Matching

Weighted Bipartite Matching

Stable Matchings(optional)

Faster Bipartite Matching(optional)

Exercises

3.3 Matchings in General Graphs

Tutte's 1-factor Theorem

f-factors of Graphs(optional)

Edmonds'Blossom Algorithm(optional)

Exercises

Chapter 4 Connectivity and Paths

4.1 Cuts and Connectivity

Connectivity

Edge-connectivity

Blocks

Exercises

4.2 k-connected Graphs

2-connected Graphs

Connectivity of Digraphs

k-connected and k-edge-connected Graphs

Applications of Menger's Theorem

Exercises

4.3 Network Flow Problems

Maximum Network Flow

Integral Flows

Supplies and Demands(optional)

Exercises

Chapter 5 Coloring of Graphs

5.1 Vertex Colorings and Upper Bounds

Definitions and Examples

Upper Bounds

Brooks'Theorem

Exercises

5.2 Structure of k-chromatic Graphs

Graphs with Large Chromatic Number

Extremal Problems and Turán's Theorem

Color-Critical Graphs

Forced Subdivisions

Exercises

5.3 Enumerative Aspects

Counting Proper Colorings

Chordal Graphs

A Hint of Perfect Graphs

Counting Acyclic Orientations(optional)

Exercises

Chapter 6 Planar Graphs

6.1 Embeddings and Euler's Formula

Drawings in the Plane

Dual Graphs

Euler's Formula

Exercises

6.2 Characterization of Planar Graphs

Preparation for Kuratowski's Theorem

Convex Embeddings

Planarity Testing(optional)

Exercises

6.3 Parameters of Planarity

Coloring of Planar Graphs

Crossing Number

Surfaces of Higher Genus(optional)

Exercises

Chapter 7 Edges and Cycles

7.1 Line Graphs and Edge-coloring

Edge-colorings

Characterization of Line Graphs(optional)

Exercises

7.2 Hamiltonian Cycles

Necessary Conditions

Sufficient Conditions

Cycles in Directed Graphs(optional)

Exercises

7.3 Planarity,Coloring,and Cycles

Tait's Theorem

Grinberg's Theorem

Snarks(optional)

Flows and Cycle Covers(optional)

Exercises

Chapter 8 Additional Topics(optional)

8.1 Perfect Graphs

The Perfect Graph Theorem

Chordal Graphs Revisited

Other Classes of Perfect Graphs

Imperfect Graphs

The Strong Perfect Graph Conjecture

Exercises

8.2 Matroids

Hereditary Systems and Examples

Properties of Matroids

The Span Function

The Dual of a Matroid

Matroid Minors and Planar Graphs

Matroid Intersection

Matroid Union

Exercises

8.3 Ramsey Theory

The Pigeonhole Principle Revisited

Ramsey's Theorem

Ramsey Numbers

Graph Ramsey Theory

Sperner's Lemma and Bandwidth

Exercises

8.4 More Extremal Problems

Encodings of Graphs

Branchings and Gossip

List Coloring and Choosability

Partitions Using Paths and Cycles

Circumference

Exercises

8.5 Random Graphs

Existence and Expectation

Properties of Almost All Graphs

Threshold Functions

Evolution and Graph Parameters

Connectivity,Cliques,and Coloring

Martingales

Exercises

8.6 Eigenvalues of Graphs

The Characteristic Polynomial

Linear Algebra of Real Symmetric Matrices

Eigenvalues and Graph Parameters

Eigenvalues of Regular Graphs

Eigenvalues and Expanders

Strongly Regular Graphs

Exercises

Appendix A Mathematical Background

Sets

Quantifiers and Proofs

Induction and Recurrence

Functions

Counting and Binomial Coefficients

Relations

The Pigeonhole Principle

Appendix B Optimization and Complexity

Intractability

Heuristics and Bounds

NP-Completeness Proofs

Exercises

Appendix C Hints for Selected Exercises

General Discussion

Supplemental Specific Hints

Appendix D Glossary of Terms

Appendix E Supplemental Reading

Appendix F References

Author Index

Subject Index