Read the original document by opening this link in a new tab.
Table of Contents
1. Preface
1.1. What is this?
1.1.1. Remarks
1.2. Notations
2. Simple graphs
2.1. Definitions
2.2. Drawing graphs
2.3. A first fact: The Ramsey number R(3, 3)=6
2.4. Degrees
2.5. Graph isomorphism
2.6. Some families of graphs
2.6.1. Complete and empty graphs
2.6.2. Path and cycle graphs
2.6.3. Kneser graphs
2.7. Subgraphs
2.8. Disjoint unions
2.9. Walks and paths
2.9.1. Definitions
2.9.2. Composing/concatenating and reversing walks
2.9.3. Reducing walks to paths
2.9.4. Remark on algorithms
2.9.5. The equivalence relation “path-connected”
2.9.6. Connected components and connectedness
2.9.7. Induced subgraphs on components
2.9.8. Some exercises on connectedness
2.10. Closed walks and cycles
2.11. The longest path trick
2.12. Bridges
2.13. Dominating sets
2.13.1. Definition and basic facts
2.13.2. The number of dominating sets
2.14. Hamiltonian paths and cycles
2.14.1. Basics
2.14.2. Sufficient criteria: Ore and Dirac
2.14.3. A necessary criterion
2.14.4. Hypercubes
2.14.5. Cartesian products
2.14.6. Subset graphs
3. Multigraphs
3.1. Definitions
3.2. Conversions
3.3. Generalizing from simple graphs to multigraphs
3.3.1. The Ramsey number R(3, 3)
3.3.2. Degrees
3.3.3. Graph isomorphisms
3.3.4. Complete graphs, paths, cycles
3.3.5. Induced submultigraphs
3.3.6. Disjoint unions
3.3.7. Walks
3.3.8. Path-connectedness
3.3.9. G\e, bridges and cut-edges
3.3.10. Dominating sets
3.3.11. Hamiltonian paths and cycles
3.3.12. Exercises
4. Digraphs and multidigraphs
4.1. Definitions
4.2. Outdegrees and indegrees
4.3. Subdigraphs
4.4. Conversions
4.4.1. Multidigraphs to multigraphs
4.4.2. Multigraphs to multidigraphs
4.4.3. Simple digraphs to multidigraphs
4.4.4. Multidigraphs to simple digraphs
4.4.5. Multidigraphs as a big tent
4.5. Walks, paths, closed walks, cycles
4.5.1. Definitions
4.5.2. Basic properties
4.5.3. Exercises
4.5.4. The adjacency matrix
4.6. Connectedness strong and weak
4.7. Eulerian walks and circuits
4.8. Hamiltonian cycles and paths
4.9. The reverse and complement digraphs
4.10. Tournaments
4.10.1. Definition
4.10.2. The Rédei theorems
4.10.3. Hamiltonian cycles in tournaments
4.10.4. Application of tournaments to the Vandermonde determinant
4.11. Exercises on tournaments
5. Trees and arborescences
5.1. Some general properties of components and cycles
5.1.1. Backtrack-free walks revisited
5.1.2. Counting components
5.2. Forests and trees
5.2.1. Definitions
5.2.2. The tree equivalence theorem
5.2.3. Summary
5.3. Leaves
5.4. Spanning trees
5.4.1. Spanning subgraphs
5.4.2. Spanning trees
5.4.3. Spanning forests
5.4.4. Existence and construction of a spanning tree
5.4.5. Applications
5.4.6. Exercises
5.4.7. Existence and construction of a spanning forest
5.5. Centers of graphs and trees
5.5.1. Distances
5.5.2. Eccentricity and centers
5.5.3. The centers of a tree
5.6. Arborescences
5.6.1. Definitions
5.6.2. Arborescences vs. trees: statement
Summary
This is a graduate-level introduction to graph theory, corresponding to a quarter-long course. It covers simple graphs, multigraphs as well as their directed analogues, and more restrictive classes such as tournaments, trees and arborescences. Among the features discussed are Eulerian circuits, Hamiltonian cycles, spanning trees, the matrix-tree and BEST theorems, proper colorings, Turan’s theorem, bipartite matching and the Menger and Gallai–Milgram theorems. The basics of network flows are introduced in order to prove Hall’s marriage theorem. Around a hundred exercises are included (without solutions).