Fall 2004 Math 412 Graph Theory sections G1U and G1G

Test 4 Material

These are the major topics to be covered on the fourth test. Most topics require foundational and background knowledge.

1. Matchings in bipartite graphs. Hall's Theorem.

2. Matchings and covers. Konig-Egervary Theorem.

3. Matchings in general graphs. Tutte's Theorem.

4. Menger's Theorems.

5. Flows in networks. Ford-Fulkerson Algorithm. Max Flow--Min Cut Theorem.

6. Integral flows (matchings in bipartite graphs, edge connectivity).

7. Colorings. Greedy algorithm for coloring.

8. Color-critical graphs and their properties ((k-1)-edge-connected etc.).

9. Brooks' Theorem.

10. Mycielski's Construction.

11. Turan's Theorem.

12. Planar and plane graphs. Dual graphs.

13. Bipartite planar graphs versus Eulerian dual graphs.

14. Euler's Formula.

15. Outerplanar graphs.

16. Kuratowski's Theorem.

17. 5-Color Theorem for planar graphs.

18. Edge colorings. Shannon's Theorem. Edge colorings of bipartite graphs.

    Back This page last modified .