Graph Theory(with hints and detailed bookmark)

Cover
Copyright
Preface
Contents
1 Graphs
1.1 Graphs and Their Representation
Definitions and Examples
Drawings of Graphs
Special Families of Graphs
Incidence and Adjacency Matrices
Vertex Degrees
Proof Technique: Counting in Two Ways
Exercises
1.2 Isomorphisms and Automorphisms
Isomorphisms
Testing for Isomorphism
Automorphisms
Labelled Graphs
Exercises
1.3 Graphs Arising from Other Structures
Polyhedral Graphs
Set Systems and Hypergraphs
Incidence Graphs
Intersection Graphs
Exercises
1.4 Constructing Graphs from Other Graphs
Union and Intersection
Cartesian Product
Exercises
1.5 Directed Graphs
Exercises
1.6 Infinite Graphs
Exercises
1.7 Related Reading
History of Graph Theory
2 Subgraphs
2.1 Subgraphs and Supergraphs
Edge and Vertex Deletion
Maximality and Minimality
Acyclic Graphs and Digraphs
Proof Technique: The Pigeonhole Principle
Exercises
2.2 Spanning and Induced Subgraphs
Spanning Subgraphs
Proof Technique: Induction
Proof Technique: Contradiction
Induced Subgraphs
Weighted Graphs and Subgraphs
Exercises
2.3 Modifying Graphs
Vertex Identification and Edge Contraction
Vertex Splitting and Edge Subdivision
Exercises
2.4 Decompositions and Coverings
Decompositions
Proof Technique: Linear Independence
Coverings
Exercises
2.5 Edge Cuts and Bonds
Edge Cuts
Bonds
Cuts in Directed Graphs
Exercises
2.6 Even Subgraphs
The Cycle and Bond Spaces
Exercises
2.7 Graph Reconstruction
The Reconstruction Conjecture
The Edge Reconstruction Conjecture
Proof Technique: Möbius Inversion
Exercises
2.8 Related Reading
Path and Cycle Decompositions
Legitimate Decks
Ultrahomogeneous Graphs
3 Connected Graphs
3.1 Walks and Connection
Walks
Connection
Proof Technique: Eigenvalues
Exercises
3.2 Cut Edges
Exercises
3.3 Euler Tours
Fleury’s Algorithm
Exercises
3.4 Connection in Digraphs
Exercises
3.5 Cycle Double Covers
The Cycle Double Cover Conjecture
The Circular Embedding Conjecture
Double Covers by Even Subgraphs
Exercises
3.6 Related Reading
Cages
4 Trees
4.1 Forests and Trees
Rooted Trees and Branchings
Proof Technique: Ordering Vertices
Exercises
4.2 Spanning Trees
Cayley's Formula
Exercises
4.3 Fundamental Cycles and Bonds
Cotrees
Exercises
4.4 Related Reading
Matroids
5 Nonseparable Graphs
5.1 Cut Vertices
Exercises
5.2 Separations and Blocks
Nonseparable Graphs
Blocks
Proof Technique: Splitting off Edges
Exercises
5.3 Ear Decompositions
Strong orientations
Exercises
5.4 Directed Ear Decompositions
Exercises
5.5 Related Reading
Even Cycle Decompositions
Matroids and Nonseparability
6 Tree-Search Algorithms
6.1 Tree-Search
Breadth-First Search and Shortest Paths
Depth-First Search
Finding the Cut Vertices and Blocks of a Graph
Exercises
6.2 Minimum-Weight Spanning Trees
The Jarník-Prim Algorithm
Exercises
6.3 Branching-Search
Finding Shortest Paths in Weighted Digraphs
Directed Depth-First Search
Finding the Strong Components of a Digraph
Exercises
6.4 Related Reading
Data Structures
7 Flows in Networks
7.1 Transportation Networks
Flows
Cuts
Exercises
7.2 The Max-Flow Min-Cut Theorem
The Ford-Fulkerson Algorithm
Exercises
7.3 Arc-Disjoint Directed Paths
Circulations
Menger's Theorem
Exercises
7.4 Related Reading
Multicommodity Flows
8 Complexity of Algorithms
8.1 Computational Complexity
The Class P
The Classes NP and co-NP
The Cook-Edmonds-Levin Conjecture
Edmonds' Conjecture
Exercises
8.2 Polynomial Reductions
Exercises
8.3 NP-Complete Problems
The Class NPC
Boolean Formulae
Satisfiability of Boolean Formulae
Proof Technique: Polynomial Reduction
NP-Hard Problems
Exercises
8.4 Approximation Algorithms
Exercises
8.5 Greedy Heuristics
The Borůvka-Kruskal Algorithm
Independence Systems
Exercises
8.6 Linear and Integer Programming
Proof Technique: Total Unimodularity
Matchings and Coverings in Bipartite Graphs
Exercises
8.7 Related Reading
Isomorphism-Completeness
9 Connectivity
9.1 Vertex Connectivity
Connectivity and Local Connectivity
Vertex Cuts and Menger's Theorem
Exercises
9.2 The Fan Lemma
Exercises
9.3 Edge Connectivity
Essential Edge Connectivity
Connectivity in Digraphs
Exercises
9.4 Three-Connected Graphs
Decomposition Trees
Contractions of Three-Connected Graphs
Expansions of Three-Connected Graphs
Exercises
9.5 Submodularity
Edge Connectivity of Vertex-Transitive Graphs
Nash-Williams' Orientation Theorem
Exercises
9.6 Gomory-Hu Trees
Determining Edge Connectivity
Exercises
9.7 Chordal Graphs
Clique Cuts
Simplicial Vertices
Tree Representations
Exercises
9.8 Related Reading
Lexicographic Breadth-First Search
Tree-Decompositions
10 Planar Graphs
10.1 Plane and Planar Graphs
The Jordan Curve Theorem
Subdivisions
Exercises
10.2 Duality
Faces
Duals
Deletion-Contraction Duality
Vector Spaces and Duality
Exercises
10.3 Euler's Formula
Exercises
10.4 Bridges
Bridges of Cycles
Unique Plane Embeddings
Exercises
10.5 Kuratowski's Theorem
Minors
Wagner's Theorem
Recognizing Planar Graphs
Exercises
10.6 Surface Embeddings of Graphs
Orientable and Nonorientable Surfaces
The Euler Characteristic
The Orientable Embedding Conjecture
Exercises
10.7 Related Reading
Graph Minors
Linkages
Brambles
Matroids and Duality
Matroid Minors
11 The Four-Colour Problem
11.1 Colourings of Planar Maps
Face Colourings
Vertex Colourings
Edge Colourings: Tait's Theorem
11.2 The Five-Colour Theorem
Exercises
11.3 Related Reading
Equivalent Forms of the Four-Colour Problem
12 Stable Sets and Cliques
12.1 Stable Sets
Stability and Clique Numbers
Shannon Capacity
Kernels
Exercises
12.2 Turán's Theorem
An Application to Combinatorial Geometry
Exercises
12.3 Ramsey's Theorem
Ramsey Numbers and Ramsey Graphs
Bounds on Ramsey Numbers
An Application to Number Theory
Exercises
12.4 The Regularity Lemma
Regular Pairs and Regular Partitions
The Erdős-Stone Theorem
Linear Ramsey Numbers
A Proof of the Regularity Lemma
Exercises
12.5 Related Reading
Hypergraph Extremal Problems
Constructions from Hypergraphs
Ramsey Theorems in Other Contexts
13 The Probabilistic Method
13.1 Random Graphs
Independent Events
Random Variables
Exercises
13.2 Expectation
Linearity of Expectation
The Crossing Lemma
Asymptotic Notation
Markov's Inequality
Exercises
13.3 Variance
Chebyshev's Inequality
Stability Numbers of Random Graphs
Exercises
13.4 Evolution of Random Graphs
Threshold Functions
Balanced Graphs
The Giant Component
Exercises
13.5 The Local Lemma
Two-Colourable Hypergraphs
Even Cycles in Directed Graphs
Linear Arboricity
Exercises
13.6 Related Reading
Probabilistic Models
Sharp Threshold Functions
Concentration Inequalities
14 Vertex Colourings
14.1 Chromatic Number
A Greedy Colouring Heuristic
Brooks' Theorem
Colourings of Digraphs
Exercises
14.2 Critical Graphs
Exercises
14.3 Girth and Chromatic Number
Mycielski's Construction
Exercises
14.4 Perfect Graphs
The Perfect Graph Theorem
The Strong Perfect Graph Theorem
Exercises
14.5 List Colourings
List Chromatic Number
Exercises
14.6 The Adjacency Polynomial
Proof Technique: The Combinatorial Nullstellensatz
Exercises
14.7 The Chromatic Polynomial
Exercises
14.8 Related Reading
Fractional Colourings
Homomorphisms and Circular Colourings
15 Colourings of Maps
15.1 Chromatic Numbers of Surfaces
Heawood's Inequality
The Map Colour Theorem
Exercises
15.2 The Four-Colour Theorem
Kempe Chains
Kempe's Erroneous Proof
Reducibility
Unavoidability
Proof Technique: Discharging
Exercises
15.3 List Colourings of Planar Graphs
Thomassen's Proof of the Five-Colour Theorem
Exercises
15.4 Hadwiger's Conjecture
Hadwiger's Conjecture
Hajós' Conjecture
Exercises
15.5 Related Reading
Near 4-Colourings of Graphs on Surfaces
16 Matchings
16.1 Maximum Matchings
Augmenting Paths
Berge's Theorem
Exercise
16.2 Matchings in Bipartite Graphs
Hall's Theorem
Matchings and Coverings
Exercise
16.3 Matchings in Arbitrary Graphs
Barriers
The Tutte-Berge Theorem
Exercise
16.4 Perfect Matchings and Factors
Tutte's Theorem
Factors
T-Joins
Exercise
16.5 Matching Algorithms
Augmenting Path Search
Egerváry's Algorithm
Blossoms
Flowers
Edmonds' Algorithm
Exercise
16.6 Related Reading
Stable Sets in Claw-Free Graphs
Transversal Matroids
Rado's Theorem
Pfaffians
17 Edge Colourings
17.1 Edge Chromatic Number
Edge Colourings of Bipartite Graphs
Exercise
17.2 Vizing's Theorem
Exercise
17.3 Snarks
Exercise
17.4 Coverings by Perfect Matchings
Fulkerson's Conjecture
Exercise
17.5 List Edge Colourings
The List Edge Colouring Conjecture
Galvin's Theorem
Exercise
17.6 Related Reading
Total Colourings
Fractional Edge Colourings
18 Hamilton Cycles
18.1 Hamiltonian and Nonhamiltonian Graphs
Tough Graphs
Hypohamiltonian Graphs
Exercise
18.2 Nonhamiltonian Planar Graphs
Grinberg's Theorem
Barnette's Conjecture
Exercise
18.3 Path and Cycle Exchanges
Path Exchanges
Cycle Exchanges
Dirac's Theorem
The Closure of a Graph
The Chvátal-Erdős Theorem
Exercise
18.4 Path Exchanges and Parity
The Lollipop Lemma
Uniquely Hamiltonian Graphs
Sheehan's Conjecture
Exercise
18.5 Hamilton Cycles in Random Graphs
Pósa's Lemma
Exercise
18.6 Related Reading
The Bridge Lemma
The Hopping Lemma
Long Paths and Cycles
19 Coverings and Packings in Directed Graphs
19.1 Coverings and Packings in Hypergraphs
Coverings and Decompositions
Packings and Transversals
Min-Max Theorems
The Erdős-Pósa Property
Exercise
19.2 Coverings by Directed Paths
The Gallai-Milgram Theorem
Berge's Path Partition Conjecture
The Path Partition Conjecture
Exercise
19.3 Coverings by Directed Cycles
Coherent Cyclic Orders
The Bessy-Thomassé Theorem
Cycle Coverings and Ear Decompositions
Exercise
19.4 Packings of Branchings
Edmonds' Branching Theorem
Exercise
19.5 Packings of Directed Cycles and Directed Bonds
Directed Bonds and Cuts
The Lucchesi-Younger Theorem
Woodall's Conjecture
Exercise
19.6 Related Reading
Packing T-Cuts
20 Electrical Networks
20.1 Circulations and Tensions
The Circulation and Tension Spaces
Circulations and Tensions in Plane Digraphs
Exercise
20.2 Basis Matrices
Exercise
20.3 Feasible Circulations and Tensions
Proof Technique: Farkas' Lemma
Finding a Feasible Circulation
Exercise
20.4 The Matrix-Tree Theorem
Exercise
20.5 Resistive Electrical Networks
Kirchhoff's Laws
Effective Resistance
Exercise
20.6 Perfect Squares
Exercise
20.7 Random Walks on Graphs
Hitting, Commute, and Cover Times
Exercise
20.8 Related Reading
Random Walks on Infinite Graphs
21 Integer Flows and Coverings
21.1 Circulations and Colourings
Nowhere-Zero Circulations and Tensions
Exercise
21.2 Integer Flows
k-Flows
Flow Number
The Flow Polynomial
Integer Flows and Covers by Even Subgraphs
Exercise
21.3 Tutte's Flow Conjectures
The Five-Flow Conjecture
The Four-Flow Conjecture
The Three-Flow Conjecture
Exercise
21.4 Edge-Disjoint Spanning Trees
The Nash-Williams-Tutte Theorem
Exercise
21.5 The Four-Flow and Eight-Flow Theorems
Uniform Covers by Even Subgraphs
Exercise
21.6 The Six-Flow Theorem
Sextuple Covers by Even Subgraphs
Jaeger‘s Conjecture
Exercise
21.7 The Tutte Polynomial
Exercise
21.8 Related Reading
Packing Bases in Matroids
The Tutte Polynomial for Matroids
Appendix A Unsolved Problems
References
General Mathematical Notation
Graph Parameters
Families of Graphs
Structures
Other Notation
Index
Appendix B Hints to Selected Exercises
Chapter 1
Chapter 2
Chapter 3
Chapter 4
Chapter 5
Chapter 6
Chapter 7
Chapter 8
Chapter 9
Chapter 10
Chapter 11
Chapter 12
Chapter 13
Chapter 14
Chapter 15
Chapter 16
Chapter 17
Chapter 18
Chapter 19
Chapter 20
Chapter 21