The catalog description for Graph Theory 1 (MATH 5340) is: "Topics include special classes of graphs, distance in graphs, graphical parameters, connectivity, Eulerian graphs, hamiltonian graphs, networks, and extremal graph theory. Theory and proof techniques will be emphasized." The catalog description for Graph Theory 2 (MATH 5450) is: "Analyze topics in planar graphs, the Four Color Theorem, vertex/edge colorings, random graphs, and contemporary research topics in graph theory." The catalog description for Mathematical Modeling Using Graph Theory (MATH 5870) is: "This course introduces the student to applied graph theory. Graph theoretical concepts will be approached as models for practical, real-world problems. The course will provide an introduction to graph modeling, integrated with applications based on emerging methods and needs. The emphasis is both on graphs as models - communication networks, for example - and on the algorithms used for obtaining information from those models." The catalog descriptions are based on the 2021-22 Graduate Catalogue. Links to notes meant to be used in Graph Theory 1 (covering Bondy and Murty Chapters 1-5) and notes for Mathematical Modeling Using Graph Theory (MATH 5870) (covering Bondy and Murty Chapters 6, 7, 8, 20, and 21) are also available.

Copies of the classnotes are on the internet in PDF format as given below. The notes and supplements may contain hyperlinks to posted webpages; the links appear in red fonts. The "Proofs of Theorems" files were prepared in Beamer. The "Printout of Proofs" are printable PDF files of the Beamer slides without the pauses.

• Chapter 9. Connectivity.
• Chapter 10. Planar Graphs.
• Chapter 11. The Four-Colour Problem.
• Chapter 12. Stable Sets and Cliques.
• Chapter 13. The Probabilistic Method.
• Chapter 14. Vertex Colourings.
• Chapter 15. Colourings of Maps.
• Chapter 16. Matchings.
• Chapter 17. Edge Colourings.
• Chapter 18. Hamilton Cycles.
• Chapter 19. Coverings and Packings in Directed Graphs.
• Additional Chapters and Topics.
• Unsolved Problems.

9. Connectivity.

• 9.1. Vertex Connectivity. Section 9.1 notes
• Supplement. Proofs from Section 9.1. Beamer file of Section 9.1 proofs
• Supplement. Printouts of Proofs from Section 9.1. Print file of Section 9.1 proofs
• 9.2. The Fan Lemma. Section 9.2 notes
• Supplement. Proofs from Section 9.2. Beamer file of Section 9.2 proofs
• Supplement. Printouts of Proofs from Section 9.2. Print file of Section 9.2 proofs
• 9.3. Edge Connectivity. Section 9.3 notes
• 9.4. Three-Connected Graphs. Section 9.4 notes
• Supplement. Proofs from Section 9.4. Beamer file of Section 9.4 proofs
• Supplement. Printouts of Proofs from Section 9.4. Print file of Section 9.4 proofs
• 9.5. Submodularity.
• 9.6. Gomory-Hu Trees.
• 9.7. Chordal Graphs. Section 9.7 notes
• Supplement. Proofs from Section 9.7. Beamer file of Section 9.7 proofs
• Supplement. Printouts of Proofs from Section 9.7. Print file of Section 9.7 proofs
• 9.8. Related Reading.
• Study Guide 9

10. Planar Graphs.

• 10.1. Plane and Planar Graphs. Section 10.1 notes
• Supplement. Proofs from Section 10.1. Beamer file of Section 10.1 proofs
• Supplement. Printouts of Proofs from Section 10.1. Print file of Section 10.1 proofs
• 10.2. Duality. Section 10.2 notes
• Supplement. Proofs from Section 10.2. Beamer file of Section 10.2 proofs
• Supplement. Printouts of Proofs from Section 10.2. Print file of Section 10.2 proofs
• 10.3. Euler's Formula. Section 10.3 notes
• Supplement. Proofs from Section 10.3. Beamer file of Section 10.3 proofs
• Supplement. Printouts of Proofs from Section 10.3. Print file of Section 10.3 proofs
• 10.4. Bridges. Section 10.4 notes
• Supplement. Proofs from Section 10.4. Beamer file of Section 10.4 proofs
• Supplement. Printouts of Proofs from Section 10.4. Print file of Section 10.4 proofs
• 10.5. Kuratowski's Theorem. Section 10.5 notes
• Supplement. Proofs from Section 10.5. Beamer file of Section 10.5 proofs
• Supplement. Printouts of Proofs from Section 10.5. Print file of Section 10.5 proofs
• Supplement. Section 10.5. Kuratowski's Theorem, Exercise 10.5.3(b). Exercise 10.5.3(b) notes
• 10.6. Surface Embeddings of Graphs. Section 10.6 notes
• 10.7. Related Reading.
• Study Guide 10

11. The Four-Colour Problem.

• 11.1. Colourings of Planar Maps. Section 11.1 notes
• Supplement. Proofs from Section 11.1. Beamer file of Section 11.1 proofs
• Supplement. Printouts of Proofs from Section 11.1. Print file of Section 11.1 proofs
• 11.2. The Five-Colour Theorem. Section 11.2 notes
• Supplement. Proofs from Section 11.2. Beamer file of Section 11.2 proofs
• Supplement. Printouts of Proofs from Section 11.2. Print file of Section 11.2 proofs
• 11.3. Related Reading.
• Study Guide 11

12. Stable Sets and Cliques.

• 12.1. Stable Sets. Section 12.1 notes
• Supplement. Proofs from Section 12.1. Beamer file of Section 12.1 proofs
• Supplement. Printouts of Proofs from Section 12.1. Print file of Section 12.1 proofs
• 12.2. Turan's Theorem. Section 12.2 notes
• Supplement. Proofs from Section 12.2. Beamer file of Section 12.2 proofs
• Supplement. Printouts of Proofs from Section 12.2. Print file of Section 12.2 proofs
• 12.3. Ramsey's Theorem. Section 12.3 notes
• Supplement. Proofs from Section 12.3. Beamer file of Section 12.1 proofs
• Supplement. Printouts of Proofs from Section 12.3. Print file of Section 12.3 proofs
• 12.4. The Regularity Lemma.
• 12.5. Related Reading.
• Study Guide 12

13. The Probabilistic Method.

• 13.1. Random Graphs. Section 13.1 notes
• 13.2. Expectation. Section 13.2 notes
• Supplement. Proofs from Section 13.2. Beamer file of Section 13.2 proofs
• Supplement. Printouts of Proofs from Section 13.2. Print file of Section 13.2 proofs
• 13.3. Variance. Section 13.3 notes
• Supplement. Proofs from Section 13.3. Beamer file of Section 13.3 proofs
• Supplement. Printouts of Proofs from Section 13.3. Print file of Section 13.3 proofs
• 13.4. Evolution of Random Graphs. Section 13.4 notes
• Supplement. Proofs from Section 13.4. Beamer file of Section 13.4 proofs
• Supplement. Printouts of Proofs from Section 13.4. Print file of Section 13.4 proofs
• 13.5. The Local Lemma. Section 13.5 notes
• Supplement. Proofs from Section 13.5. Beamer file of Section 13.5 proofs
• Supplement. Printouts of Proofs from Section 13.5. Print file of Section 13.5 proofs
• 13.6. Related Reading. Section 13.6 notes
• Study Guide 9

14. Vertex Colourings.

• 14.1. Chromatic Number. Section 14.1 notes
• Supplement. Proofs from Section 14.1. Beamer file of Section 14.1 proofs
• Supplement. Printouts of Proofs from Section 14.1. Print file of Section 14.1 proofs
• 14.2. Critical Graphs. Section 14.2 notes
• Supplement. Proofs from Section 14.2. Beamer file of Section 14.2 proofs
• Supplement. Printouts of Proofs from Section 14.2. Print file of Section 14.2 proofs
• 14.3. Girth and Chromatic Number. Section 14.3 notes
• Supplement. Proofs from Section 14.3. Beamer file of Section 14.3 proofs
• Supplement. Printouts of Proofs from Section 14.3. Print file of Section 14.3 proofs
• 14.4. Perfect Graphs. Section 14.14notes
• Supplement. Proofs from Section 14.4. Beamer file of Section 14.4 proofs
• Supplement. Printouts of Proofs from Section 14.4. Print file of Section 14.4 proofs
• 14.5. List Colouring. Section 14.5 notes
• Supplement. Proofs from Section 14.5. Beamer file of Section 14.5 proofs
• Supplement. Printouts of Proofs from Section 14.5. Print file of Section 14.5 proofs
• 14.6. The Adjacency Polynomial. Section 14.6 notes
• Supplement. Proofs from Section 14.6. Beamer file of Section 14.6 proofs
• Supplement. Printouts of Proofs from Section 14.6. Print file of Section 14.6 proofs
• 14.7. The Chromatic Polynomial. Section 14.7 notes
• Supplement. Proofs from Section 14.7. Beamer file of Section 14.7 proofs
• Supplement. Printouts of Proofs from Section 14.7. Print file of Section 14.7 proofs
• 14.8. Related Reading.
• Study Guide 14

15. Colourings of Maps.

• 15.1. Chromatic Numbers of Surfaces. Section 15.1 notes
• Supplement. Proofs from Section 15.1. Beamer file of Section 15.1 proofs
• Supplement. Printouts of Proofs from Section 15.1. Print file of Section 15.1 proofs
• 15.2. The Four-Colour Theorem. Section 15.2 notes
• Supplement. Proofs from Section 15.2. Beamer file of Section 15.2 proofs
• Supplement. Printouts of Proofs from Section 15.2. Print file of Section 15.2 proofs
• Supplement. The Four-Colour Theorem: A History, Part 1. Four-Colour Theorem History 1
• Supplement. The Four-Colour Theorem: A History, Part 2. Four-Colour Theorem History 2
• 15.3. List Colourings of Planar Graphs. Section 15.3 notes
• Supplement. Proofs from Section 15.3. Beamer file of Section 15.3 proofs
• Supplement. Printouts of Proofs from Section 15.3. Print file of Section 15.3 proofs
• 15.4. Hadwiger's Conjecture. Section 15.4 notes
• Supplement. Proofs from Section 15.4. Beamer file of Section 15.4 proofs
• Supplement. Printouts of Proofs from Section 15.4. Print file of Section 15.4 proofs
• 15.5. Related Reading.
• Study Guide 15

16. Matchings.

• 16.1. Maximum Matchings. Section 16.1 notes
• Supplement. Proofs from Section 16.1. Beamer file of Section 16.1 proofs
• Supplement. Printouts of Proofs from Section 16.1. Print file of Section 16.1 proofs
• 16.2. Matchings in Bipartite Graphs. Section 16.2 notes
• Supplement. Proofs from Section 16.2. Beamer file of Section 16.2 proofs
• Supplement. Printouts of Proofs from Section 16.2. Print file of Section 16.2 proofs
• 16.3. Matchings in Arbitrary Graphs. Section 16.3 notes
• Supplement. Proofs from Section 16.3. Beamer file of Section 16.3 proofs
• Supplement. Printouts of Proofs from Section 16.3. Print file of Section 16.3 proofs
• 16.4. Perfect Matchings and Factors. Section 16.4 notes
• Supplement. Proofs from Section 16.4. Beamer file of Section 16.4 proofs
• Supplement. Printouts of Proofs from Section 16.4. Print file of Section 16.4 proofs
• 16.5. Matching Algorithms.
• 16.6. Related Reading.
• Study Guide 16

17. Edge Colourings.

• 17.1. Edge Chromatic Number. Section 17.1 notes
• Supplement. Proofs from Section 17.1. Beamer file of Section 17.1 proofs
• Supplement. Printouts of Proofs from Section 17.1. Print file of Section 17.1 proofs
• 17.2. Vizing's Theorem. Section 17.2 notes
• Supplement. Proofs from Section 17.2. Beamer file of Section 17.2 proofs
• Supplement. Printouts of Proofs from Section 17.2. Print file of Section 17.2 proofs
• 17.3. Snarks. Section 17.3 notes
• 17.4. Coverings by Perfect Matchings. Section 17.4 notes
• 17.5. List Edge Colourings. Section 17.5 notes
• Supplement. Proofs from Section 17.5. Beamer file of Section 17.5 proofs
• Supplement. Printouts of Proofs from Section 17.5. Print file of Section 17.5 proofs
• 17.6. Related Reading. Section 17.6 notes (This contains an introduction to the Total Colouring Conjecture.)
• Supplement. Proofs from Section 17.6. Beamer file of Section 17.6 proofs
• Supplement. Printouts of Proofs from Section 17.6. Print file of Section 17.6 proofs
• Study Guide 9

18. Hamilton Cycles.

• 18.1. Hamiltonian and NonHamiltonian Graphs. Section 18.1 notes
• Supplement. Proofs from Section 18.1. Beamer file of Section 18.1 proofs
• Supplement. Printouts of Proofs from Section 18.1. Print file of Section 18.1 proofs
• 18.2. NonHamiltonian Planar Graphs.
• 18.3. Path and Cycle Exchanges.
• 18.4. Path Exchanges and Parity.
• 18.5. Hamilton Cycles in Random Graphs.
• 18.6. Related Reading.
• Study Guide 18.

19. Coverings and Packings in Directed Graphs.

• 19.1. Coverings and Packings in Hypergraphs.
• 19.2. Coverings by Directed Paths.
• 19.3. Coverings by Directed Cycles.
• 19.4. Packings of Branchings.
• 19.5. Packings of Directed Cycles and Directed Bonds.
• 19.6. Related Reading.
• Study Guide 19.

Additional Chapters and Topics.

• Chapter 1. Graphs.
• Chapter 2. Subgraphs.
• Chapter 3. Connected Graphs.
• Chapter 4. Trees.
• Chapter 5. Nonseparable Graphs.
• Chapter 6. Tree-Search Algorithms.
• Chapter 7. Flow in Networks.
• Chapter 8. Complexity of Algorithms.
• Chapter 20. Electrical Networks.
• Chapter 21. Integer Flows and Coverings.

Unsolved Problems.

Return to Bob Gardner's home page