Fall 2004 Math 412 Graph Theory sections G1U and G1G

Test 2 Material

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

1. De Bruijn graphs.

2. Extremal problems on graphs. Mantel's Theorem.

3. Graphic sequences. A theorem on such sequences.

4. Trees, characterizations of trees.

5. Centers of trees.

6. Prufer codes, Cayley's formula.

7. Counting spanning trees in graphs.

8. Minimum spanning trees. Algorithms of Kruskal and Prim.

9. Shortest Path Problem. Dijkstra's Algorithm.

10. Kings in tournaments.

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

12. Matchings and covers. Konig-Egervary Theorem.

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

14. Algorithm for finding maximum matchings in bipartite graphs.

15. Stable matchings.

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

17. Berge-Tutte Formula and theorems of Petersen.

18. Connectivity and edge connectivity.

    Back This page last modified .