A good way to study for the exam is to go through old homework problems, including the suggested problems.

List of topics - you should be familiar with the following topics and at least the main ideas behind all of the proofs.

Math 412 - Test 2 topics

• Characterization of tree (Theorem 2.1.4)
• 2.1.5-8
• Jordan's Theorem - The center of a tree is a vertex or edge (2.1.13)
• Weiner index minimized by stars and maximized by paths (2.1.14-2.1.16)
• Cayley's formula - Prufer codes Theorem 2.2.3 and Corollary (2.2.4)
• recurrence for the number of spanning trees Proposition (2.2.8)
• Graceful labelings
• 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)
• Dijkstra's algorithm and the proof that Dijkstra's Algorithm is correct
• 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)
• 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)

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

• graphs, simple graphs, independent sets, cliques, complement, Isomorphism of graphs, self-complementary graphs, decompositions
• Representations of graphs: adjacency and incidence matrices.
• strong induction, connectivity, cut-edges, cut-vertices, 1.2.5, 1.2.11, 1.2.14, 1.3.15
• Walks, Path, Trails, cycles, trails, Lemma 1.2.15 in the book, Lemma 1.2.25, Proposition 1.2.27, Eulerian circuits and trails, theorem on Eulerian circuits (1.2.26).
• Bipartite graphs. A characterization of bipartite graphs Konig's Theorem (Theorem 1.2.18),
• Degree sum formula 1.3.3, 1.3.4, 1.3.5 and 1.3.9
• Definition of the hypercube
• Extremal problems on graphs. 1.3.13, 1.3.19, Mantel's Theorem (1.3.23)
• Graphic sequences. Havel-Hakimi (Theorem 1.3.31)
• Directed graphs: degrees, connectivity, adjacency and incidence matrices, Eulerian circuits, de Brujin graphs (Theorem 1.4.26).
• Tournaments, kings in tournaments (Proposition 1.4.30).