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. These notes have not been classroom tested and may have typographical errors.

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." This class was originally part of the online certificate program in Mathematical Modeling in Biosciences Graduate Certificate. This program is no longer active, but a description can be found here in the 2014-15 Graduate catalog.

A more appropriate catalog description for Mathematical Modeling Using Graph Theory (MATH 5870) based on these notes might be: "This course introduces the student to applied graph theory. Emphasis is on algorithms, especially tree-search algorithms, and the complexity of algorithms. Polynomial-time algorithms and the classes NP-complete and NP-hard are presented. The Max-Flow and Min-Cut Theorem is addressed in flows in networks. Integer flow and electrical networks are explored."

The text used in these notes is the same as the text used in Graph Theory 1 (MATH 5340) and Graph Theory 2 (MATH 5450). Notes for these classes are also online: Graph Theory 1 notes and Graph Theory 2 notes. 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 course descriptions are based on the 2021-22 Graduate Catalogue.

• Chapter 6. Tree-Search Algorithms.
• Chapter 7. Flows in Networks.
• Chapter 8. Complexity of Algorithms.
• Chapter 20. Electrical Networks.
• Chapter 21. Integer Flows and Coverings.
• Additional Chapters and Topics.

6. Tree-Search Algorithms. Chapter 6 notes

• 6.1. Tree-Search. Section 6.1 notes
• Supplement. Proofs from Section 6.1. Beamer file of Section 6.1 proofs
• Supplement. Printouts of Proofs from Section 6.1. Print file of Section 6.1 proofs
• Supplement. An illustration of the Breadth First Search Algorithm. Breadth First Search in PowerPoint
• 6.2. Minimum-Weight Spanning Trees. Section 6.2 notes
• Supplement. Proofs from Section 6.2. Beamer file of Section 6.2 proofs
• Supplement. Printouts of Proofs from Section 6.2. Print file of Section 6.2 proofs
• 6.3. Branching-Search.
• 6.4. Related Reading.
• Study Guide 6.

7. Flow in Networks.

• 7.1. Transportation Networks.
• 7.2. The Max-Flow Min-Cut Theorem.
• 7.3. Arc-Disjoint Directed Paths.
• 7.4. Related Reading.
• Study Guide 7.

8. Complexity of Algorithms.

• 8.1. Computational Complexity. Section 8.1 notes
• 8.2. Polynomial Reductions.
• 8.3. NP-Complete Problems.
• 8.4. Approximation Algorithms.
• 8.5. Greedy Heuristics.
• 8.6. Linear and Integer Programming.
• 8.7. Related Reading.
• Study Guide 8.

20. Electrical Networks.

• 20.1. Circulations and Tensions.
• 20.2. Basic Matrices.
• 20.3. Feasible Circulations and Tensions.
• 20.4. The Matrix-Tree Theorem.
• 20.5. Resistive Electrical Networks.
• 20.6. Perfect Squares.
• 20.7. Random Walks on Graphs.
• 20.8. Related Reading.
• Study Guide 20.

21. Integer Flows and Coverings.

• 21.1. Circulations and Colourings.
• 21.2. Integer Flows.
• 21.3. Tutte's Flow Conjectures.
• 21.4. Edge-Disjoint Spanning Trees.
• 21.5. The Four-Flow and Eight-Flow Theorems.
• 21.6. The Six-Flow Theorem.
• 21.7. The Tutte Polynomial.
• 21.8. Related Reading.
• Study Guide 21.

Additional Chapters and Topics.

• Chapter 1. Graphs.
• Chapter 2. Subgraphs.
• Chapter 3. Connected Graphs.
• 3.3. Euler Tours. Section 3.3 notes (This section includes includes Fleury's Algorithm to find an Euler tour.)
• Supplement. Proofs from Section 3.3. Beamer file of Section 3.1 proofs
• Supplement. Printouts of Proofs from Section 3.3. Print file of Section 3.1 proofs
• Chapter 4. Trees.
• Chapter 5. Nonseparable Graphs.
• Chapter 9. Connectivity.
• Chapter 10. Planar Graphs.
• 10.5. Kuratowski's Theorem. Section 10.5 notes (This section includes includes the Planarity Recognition and Embedding algorithm.)
• 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
• Chapter 11. The Four-Colour Problem.
• Chapter 12. Stable Sets and Cliques.
• Chapter 13. The Probabilistic Method.
• Chapter 14. Vertex Colourings.
• 14.1. Chromatic Number. Section 14.1 notes (This section includes the Greedy Colouring Heuristic.)
• 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
• Chapter 15. Colourings of Maps.
• Chapter 16. Matchings.
• 16.1. Maximum Matchings. Section 16.1 notes (This section includes a discussion of the Assignment Problem or the "Scheduling Problem.")
• 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.5. Matching Algorithms.
• Chapter 17. Edge Colourings.
• Chapter 18. Hamilton Cycles.
• Chapter 19. Coverings and Packings in Directed Graphs.
• Unsolved Problems.

Return to Bob Gardner's home page