Fall 2004 Math 412 Graph Theory sections G1U and G1G

Final Exam Topics

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

1. Bipartite graphs. A characterization of bipartite graphs.

2. Isomorphism of graphs.

3. Representations of graphs: adjacency and incidence matrices.

4. Eulerian circuits and trails. Euler Theorem.

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

6. Graphic sequences. A theorem on such sequences.

7. Directed graphs: degrees, connectivity, Eulerian circuits, de Bruijn graphs.

8. Tournaments, kings in tournaments.

9. Trees, characterizations of trees.

10. Centers of trees.

11. Prufer codes, Cayley's formula.

12. Counting spanning trees in graphs.

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

14. Shortest Path Problem. Dijkstra's Algorithm.

15. Kings in tournaments.

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

17. Matchings and covers. Konig-Egervary Theorem.

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

19. Algorithm for finding maximum matchings in bipartite graphs.

20. Stable matchings.

21. Matchings in general graphs. Tutte's 1-factor Theorem.

22. Berge-Tutte Formula and theorems of Petersen.

23. Connectivity and edge connectivity.

24. A characterization of 2-connected graphs.

25. Ear decomposition.

26. Menger's Theorems.

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

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

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

30. Colorings. Colorings of Cartesian products of graphs.

31. Greedy algorithm for coloring.

32. Coloring of interval graphs.

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

34. Brooks' Theorem.

35. Mycielski's Construction.

36. Turan's Theorem.

37. Planar and plane graphs. Dual graphs.

38. Bipartite planar graphs versus Eulerian dual graphs.

39. Euler's Formula.

40. Outerplanar graphs.

41. Kuratowski's Theorem.

42. 5-Color Theorem for planar graphs. Statement of 4-Color Theorem.

43. Edge colorings. Edge colorings of bipartite graphs.

44. Shannon's Theorem. Statement of Vizing's Theorem.

45. Hamiltonian cycles.

46. Dirac's Thm. Ore's Thm.

47. Hamiltonian closure and Bondy-Chvatal Theorem.

48. Chvatal's Theorem. Chvatal-Erdos Theorem.

49. Tait's Theorem.

    Back This page last modified .