Math 412 Old topic - These topics may appear on test 2

• Isomorphism of graphs.
• Representations of graphs: adjacency and incidence matrices.
• Walks, Path, Trails, cycles, walks trails, Lemma 1.2.15 in the book, Lemma 1.2.25, Proposition 1.2.27, Eulerian circuits and trails. Euler's Theorem (1.2.26).
• Bipartite graphs. A characterization of bipartite graphs (Theorem 1.2.18).
• Extremal problems on graphs. Mantel's Theorem (1.3.23), Turán's theorem (5.2.9)
• Graphic sequences. Havel-Hakimi (Theorem 1.3.31)
• Directed graphs: degrees, connectivity, Eulerian circuits, de Bruijn graphs (Theorem 1.4.26).
• Tournaments, kings in tournaments (Proposition 1.4.30).
• Trees, characterizations of trees (Theorem 2.1.4, Corollary 2.1.5).
• Distances in graphs. Centers of trees (Theorem 2.1.3).

Math 412 - Test 2 topics

• Cayley's formula (Theorem 2.2.3)
• recurrence for the number of spanning trees Proposition (2.2.8)
• Matrix Tree theorem (Theorem 2.2.12)
• minimum spanning trees, Kruskal's Algorithm and proof that Kruskal's algorithm is correct (Theorem 2.3.3)
• Every component of the symmetric difference of two matchings is a path or even cycle (Lemma 3.1.9)
• A matching M in a graph G is maximum if and only if M has no M-augmenting paths (Theorem 3.1.10)
• Hall's Theorem (Theorem 3.1.11) and applications
• Marriage theorem (Theorem 3.1.13)
• Stable marriage theorem - Gale-Shapley (Theorem 3.2.18)
• König, Egerváry "If G is bipartite, then α'(G) = β(G)"
• α(G) + β(G) = n(G) (Lemma 3.1.21)
• If G has no isolated vertices, then α'(G) + β'(G) = n(G) (Theorem 3.1.22)
• If G is bipartite without isolated vertices, then α(G) = β'(G) (Corollary 3.1.24)
• Tutte's Theorem (3.3.3)
• Petersen's Theorem (3.3.8)
• Berge-Tutte formula (3.3.7)