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

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

Note that Tutte's Theorem and the Berge-Tutte are topics on this exam (Tutte's Theorem was a topic on exam 2 as well).

• Tutte's Theorem (3.3.3)
• Berge-Tutte Formula (3.3.7)
• Connectivity, edge-connectivity and associated definitions: separating set, k-connected, connectivity of a graph, disconnecting set, edge connectivity, edge cut, etc.
• Example 4.1.3 - Connectivity of the hypercube
• Example 4.1.4 and Theorem 4.1.5
• (Theorem 4.1.9) κ(G) <= κ'(G) <= δ(G)
• Theorem 4.1.11 "if G is 3-regular κ(G) = κ'(G)"
• bond and block definitions
• Theorem 4.2.4
• Theorem 4.2.17 (Menger's Theorem)
• Definition 4.2.18 - Line graph
• Theorem 4.2.19 (Edge version of Menger's Theorem)
• Theorem 4.2.21 (Global versions of Menger's Theorem)
• Definition 4.2.22 (Fan), Theorem 4.2.23 (Fan Lemma)
• Definitions related to flows, value of a flow, Augmenting path, tolerance of path, definition of a source/sink cut, the capacity of a cut, flow out of and into a set
• Lemma 4.3.5, Lemma 4.3.7, Corollary 4.3.8 (Weak Duality)
• The dual problem of max-flow is min-cut
• Algorithm 4.3.9 (Ford-Fulkerson labeling algorithm)
• Theorem 4.3.11 (Max-flow/min-cut Theorem, Ford-Fulkerson),

• 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).
• 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)