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 prerequisites are "admission to the math graduate program or permission," but a background in theorem proving is essential.

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 descriptions are based on the 2021-22 Graduate Catalogue. Links to notes meant to be used in Graph Theory 2 (covering Bondy and Murty Chapters 9-13) 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.

1. Chapter 1. Graphs.
2. Chapter 2. Subgraphs.
3. Chapter 3. Connected Graphs.
4. Chapter 4. Trees.
5. Chapter 5. Nonseparable Graphs.
6. Additional Chapters and Topics.

1. Graphs. Chapter 1 notes

• 1.1. Graphs and Their Representation. Section 1.1 notes
• Supplement. Proofs from Section 1.1. Beamer file of Section 1.1 proofs
• Supplement. Printouts of Proofs from Section 1.1. Print file of Section 1.1 proofs
• 1.2. Isomorphisms and Automorphisms. Section 1.2 notes
• 1.3. Graphs Arising from Other Structures. Section 1.3 notes
• 1.4. Constructing Graphs from Other Graphs. Section 1.4 notes
• 1.5. Directed Graphs. Section 1.5 notes
• 1.6. Infinite Graphs. Section 1.6 notes
• 1.7. Related Reading. Section 1.7 notes
• Study Guide 1

2. Subgraphs.

• 2.1. Subgraphs and Supergraphs. Section 2.1 notes
• Supplement. Proofs from Section 2.1. Beamer file of Section 2.1 proofs
• Supplement. Printouts of Proofs from Section 2.1. Print file of Section 2.1 proofs
• 2.2. Spanning and Induced Subgraphs. Section 2.2 notes
• Supplement. Proofs from Section 2.2. Beamer file of Section 2.2 proofs
• Supplement. Printouts of Proofs from Section 2.2. Print file of Section 2.2 proofs
• 2.3. Modifying Graphs. Section 2.3 notes
• 2.4. Decompositions and Coverings. Section 2.4 notes
• Supplement. Proofs from Section 2.4. Beamer file of Section 2.4 proofs
• Supplement. Printouts of Proofs from Section 2.4. Print file of Section 2.4 proofs
• Supplement. Graph Decompositions: Triple Systems. Triple Systems notes
• Supplement. Proofs from Graph Decompositions. Beamer file of Triple Systems proofs
• Supplement. Printouts of Proofs from Graph Decompositions. Print file of Triple Systems proofs
• Supplement. What the Hell do Graph Decompositions have to do with Experimental Designs? Graph Decompositions and Experimental Designs talk in PowerPoint
• 2.5. Edge Cuts and Bonds. Section 2.5 notes
• Supplement. Proofs from Section 2.5. Beamer file of Section 2.5 proofs
• Supplement. Printouts of Proofs from Section 2.5. Print file of Section 2.5 proofs
• 2.6. Even Subgraphs. Section 2.1 notes
• Supplement. Proofs from Section 2.6. Beamer file of Section 2.6 proofs
• Supplement. Printouts of Proofs from Section 2.6. Print file of Section 2.6 proofs
• Supplement. Circulations and Potential Differences. Circulations and Potential Differences notes
• Supplement. Proofs from Supplement. Beamer file of Circulations and Potential Differences proofs
• Supplement. Printouts of Proofs from Supplement. Print file of Circulations and Potential Differences proofs
• 2.7. Graph Reconstruction. Section 2.7 notes
• Supplement. Proofs from Section 2.7. Beamer file of Section2.7 proofs
• Supplement. Printouts of Proofs from Section 2.7. Print file of Section 2.8 proofs
• 2.8. Related Reading.
• Study Guide 2

3. Connected Graphs.

• 3.1. Walks and Connection. Section 3.1 notes
• Supplement. Proofs from Section 3.1. Beamer file of Section 3.1 proofs
• Supplement. Printouts of Proofs from Section 3.1. Print file of Section 3.1 proofs
• 3.2. Cut Edges. Section 3.2 notes
• Supplement. Proofs from Section 3.2. Beamer file of Section 3.2 proofs
• Supplement. Printouts of Proofs from Section 3.2. Print file of Section 3.2 proofs
• 3.3. Euler Tours. Section 3.3 notes
• Supplement. Proofs from Section 3.3. Beamer file of Section 3.3 proofs
• Supplement. Printouts of Proofs from Section 3.3. Print file of Section 3.3 proofs
• 3.4. Connection in Digraphs. Section 3.4 notes
• Supplement. Proofs from Section 3.4. Beamer file of Section 3.4 proofs
• Supplement. Printouts of Proofs from Section 3.4. Print file of Section 3.4 proofs
• 3.5. Cycle Double Covers. Section 3.5 notes
• Supplement. Proofs from Section 3.5. Beamer file of Section 3.5 proofs
• Supplement. Printouts of Proofs from Section 3.5. Print file of Section 3.5 proofs
• 3.6. Related Reading.
• Study Guide 3

4. Trees.

• 4.1. Forests and Trees. Section 4.1 notes
• Supplement. Proofs from Section 4.1. Beamer file of Section 4.1 proofs
• Supplement. Printouts of Proofs from Section 4.1. Print file of Section 4.1 proofs
• 4.2. Spanning Trees. Section 4.2 notes
• Supplement. Proofs from Section 4.2. Beamer file of Section 4.2 proofs
• Supplement. Printouts of Proofs from Section 4.2. Print file of Section 4.2 proofs
• Supplement. The Number of Spanning Trees. Number of Spanning Trees notes
• Supplement. Proofs from Supplement. Beamer file of Number of Spanning Trees proofs
• Supplement. Printouts of Proofs from Supplement. Print file of Number of Spanning Tree proofs
• 4.3. Fundamental Cycles and Bonds. Section 4.3 notes
• Supplement. Proofs from Section 4.3. Beamer file of Section 4.3 proofs
• Supplement. Printouts of Proofs from Section 4.3. Print file of Section 4.3 proofs
• 4.4. Related Reading.
• Study Guide 4

5. Nonseparable Graphs.

• 5.1. Cut Vertices. Section 5.1 notes
• Supplement. Proofs from Section 5.1. Beamer file of Section 5.1 proofs
• Supplement. Printouts of Proofs from Section 5.1. Print file of Section 5.1 proofs
• 5.2. Separations and Blocks. Section 5.2 notes
• Supplement. Proofs from Section 5.2. Beamer file of Section 5.2 proofs
• Supplement. Printouts of Proofs from Section 5.2. Print file of Section 5.2 proofs
• 5.3. Ear Decompositions. Section 5.3 notes
• Supplement. Proofs from Section 5.3. Beamer file of Section 5.3 proofs
• Supplement. Printouts of Proofs from Section 5.3. Print file of Section 5.3 proofs
• 5.4. Directed Ear Decompositions.
• 5.5. Related Reading.
• Study Guide 5

Additional Chapters and Topics.

• Chapter 6. Tree-Search Algorithms.
• Chapter 7. Flows in Networks.
• Chapter 8. Complexity of Algorithms.
• 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.
• Chapter 20. Electrical Networks.
• Chapter 21. Integer Flows and Coverings.
• Unsolved Problems.

Return to Bob Gardner's home page