Completely reorganized chapters on traversability, connectivi
Table of Contents
1 Graphs
1.1 Fundamentals
1.2 Isomorphism
1.3 Families of graphs
1.4 Operations on graphs
1.5 Degree sequences
1.6 Path and cycles
1.7 Connected graphs and distance
1.8 Trees and forests
1.9 Multigraphs and pseudographs
2 Digraphs
2.1 Fundamentals
2.2 Strongly connected digraphs
2.3 Tournaments
2.4 Score sequences
3 Traversability
3.1 Eulerian graphs and digraphs
3.2 Hamiltonian graphs
3.3 Hamiltonian digraphs
3.4 Highly hamiltonian graphs
3.5 Graph powers
4 Connectivity
4.1 Cut-vertices, bridges, and blocks
4.2 Vertex connectivity
4.3 Edge-connectivity
4.4 Menger's theorem
5 Planarity
5.1 Euler's formula
5.2 Characterizations of planarity
5.3 Hamiltonian planar graphs
5.4 The crossing number of a graph
6 Coloring
6.1 Vertex coloring
6.2 Edge coloring
6.3 Critical and perfect graphs
6.4 Maps and planar graphs
7 Flows
7.1 Networks
7.2 Max-flow min-cut theorem
7.3 Menger's theorems for digraphs
7.4 A connection to coloring
8 Factors and covers
8.1 Matchings and 1-factors
8.2 Independence and covers
8.3 Domination
8.4 Factorizations and decompositions
8.5 Labelings of graphs
9 Extremal graph theory
9.1 Avoiding a complete graph
9.2 Containing cycles and trees
9.3 Ramsey theory
9.4 Cages and Moore graphs
10 Embeddings
10.1 The genus of a graph
10.2 2-Cell embeddings of graphs
10.3 The maximum genus of a graph
10.4 The graph minor theorem
11 Graphs and algebra
11.1 Graphs and matrices
11.2 The automorphism group
11.3 Cayley color graphs
11.4 The reconstruction problem
