Fall 2004 Math 412 Graph Theory sections G1U and G1G

Test 3 Material

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

1. Graphic sequences. A theorem on such sequences.

2. Prufer codes, Cayley's formula.

3. Counting spanning trees in graphs.

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

5. Matchings and covers. Konig-Egervary Theorem.

6. Gallai's Theorem (edge covers and matchings).

7. Algorithm for finding maximum matchings in bipartite graphs.

8. Stable matchings.

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

10. Connectivity and edge connectivity.

11. A characterization of 2-connected graphs.

12. Ear decomposition.

13. Menger's Theorems(!).

14. Flows in networks. Decomposition of every flow into flows along cycles and s,t-paths.

15. Ford-Fulkerson Algorithm. Max Flow--Min Cut Theorem.

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

17. Colorings. Colorings of Cartesian products of graphs.

18. Greedy algorithm for coloring.

19. Coloring of interval graphs.

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

21. Brooks' Theorem.

22. Mycielski's Construction.

    Back This page last modified .