Text in Mathematics-Graph Theory by J.A. Bondy and U.S.R. Murty

 Graph Theory 1 - Class Notes From Graph Theory J. A. Bondy and U. S. R. Murty, Graduate Texts in Mathematics 244 (Springer, 2008)

(By MRF Publications)

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. Links to additional notes meant to be used in Graph Theory 2 are also available.

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: "Advanced topics in graph theory will be presented. This course is designed to bring students to the forefront of current research in the field."

1. Chapter 1. Graphs.
2. Chapter 2. Subgraphs.
3. Chapter 3. Connected Graphs.
4. Chapter 4. Trees.
5. Chapter 5. Nonseparable Graphs.
6. Chapter 6. Tree-Search Algorithms.
7. Chapter 7. Flows in Networks.
8. Chapter 8. Complexity of Algorithms.
9. Chapter 9. Connectivity.
10. Chapter 10. Planar Graphs.
11. Additional Chapters and Topics.

1. Graphs. PDF

• 1.1. Graphs and Their Representation. PDF
• Supplement. Proofs from Section 1.1. PDF (prepared in Beamer).
• Supplement. Printouts of Proofs from Section 1.1. PDF
• 1.2. Isomorphisms and Automorphisms. PDF
• 1.3. Graphs Arising from Other Structures. PDF
• 1.4. Constructing Graphs from Other Graphs. PDF
• 1.5. Directed Graphs. PDF
• 1.6. Infinite Graphs. PDF
• 1.7. Related Reading. PDF
• Study Guide 1. PDF

2. Subgraphs.

• 2.1. Subgraphs and Supergraphs. PDF
• Supplement. Proofs from Section 2.1. PDF (prepared in Beamer).
• Supplement. Printouts of Proofs from Section 2.1. PDF
• 2.2. Spanning and Induced Subgraphs. PDF
• Supplement. Proofs from Section 2.2. PDF (prepared in Beamer).
• Supplement. Printouts of Proofs from Section 2.2. PDF
• 2.3. Modifying Graphs. PDF
• 2.4. Decompositions and Coverings. PDF
• Supplement. Proofs from Section 2.4. PDF (prepared in Beamer).
• Supplement. Printouts of Proofs from Section 2.4. PDF
• Supplement. Graph Decompositions: Triple Systems. PDF
• Supplement. Proofs from Graph Decompositions. PDF (prepared in Beamer).
• Supplement. Printouts of Proofs from Graph Decompositions. PDF
• 2.5. Edge Cuts and Bonds. PDF
• Supplement. Proofs from Section 2.5. PDF (prepared in Beamer).
• Supplement. Printouts of Proofs from Section 2.5. PDF
• 2.6. Even Subgraphs. PDF
• Supplement. Proofs from Section 2.6. PDF (prepared in Beamer).
• Supplement. Printouts of Proofs from Section 2.6. PDF
• 2.7. Graph Reconstruction. PDF
• Supplement. Proofs from Section 2.7. PDF (prepared in Beamer).
• Supplement. Printouts of Proofs from Section 2.7. PDF
• 2.8. Related Reading.
• Study Guide 2. PDF

3. Connected Graphs.

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

4. Trees.

• 4.1. Forests and Trees. PDF
• Supplement. Proofs from Section 4.1. PDF (prepared in Beamer).
• Supplement. Printouts of Proofs from Section 4.1. PDF
• 4.2. Spanning Trees. PDF
• Supplement. Proofs from Section 4.2. PDF (prepared in Beamer).
• Supplement. Printouts of Proofs from Section 4.2. PDF
• 4.3. Fundamental Cycles and Bonds. PDF
• Supplement. Proofs from Section 4.3. PDF (prepared in Beamer).
• Supplement. Printouts of Proofs from Section 4.3. PDF
• 4.4. Related Reading.
• Study Guide 4. PDF

5. Nonseparable Graphs.

• 5.1. Cut Vertices. PDF
• Supplement. Proofs from Section 5.1. PDF (prepared in Beamer).
• Supplement. Printouts of Proofs from Section 5.1. PDF
• 5.2. Separations and Blocks.
• 5.3. Ear Decompositions.
• 5.4. Directed Ear Decompositions.
• 5.5. Related Reading.
• Study Guide 5.

6. Tree-Search Algorithms.

• 6.1. Tree-Search.
• 6.2. Minimum-Weight Spanning Trees.
• 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.
• 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.

9. Connectivity.

• 9.1. Vertex Connectivity.
• 9.2. The Fan Lemma.
• 9.3. Edge Connectivity.
• 9.4. Three-Connected Graphs.
• 9.5. Submodularity.
• 9.6. Gomory-Hu Trees.
• 9.7. Chordal Graphs.
• 9.8. Related Reading.
• Study Guide 9.

10. Planar Graphs.

• 10.1. Plane and Planar Graphs. PDF
• Supplement. Proofs from Section 10.1. PDF (prepared in Beamer).
• Supplement. Printouts of Proofs from Section 10.1. PDF
• 10.2. Duality. PDF
• Supplement. Proofs from Section 10.2. PDF (prepared in Beamer).
• Supplement. Printouts of Proofs from Section 10.2. PDF
• 10.3. Euler's Formula. PDF
• Supplement. Proofs from Section 10.3. PDF (prepared in Beamer).
• Supplement. Printouts of Proofs from Section 10.3. PDF
• 10.4. Bridges. PDF
• Supplement. Proofs from Section 10.4. PDF (prepared in Beamer).
• Supplement. Printouts of Proofs from Section 10.4. PDF
• 10.5. Kuratowski's Theorem (partial). PDF
• Supplement. Proofs from Section 10.5. PDF (prepared in Beamer).
• Supplement. Printouts of Proofs from Section 10.5. PDF
• 10.6. Surface Embeddings of Graphs.
• 10.7. Related Reading.
• Study Guide 10.

Additional Chapters and Topics.

• 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.

CLICK HERE TO DOWNLOAD