New topics for final exam

• Kuratowski's Theorem and related defintions, K-graph, Maximal planar graph, minimal nonplanar graph, subdivision, branch vertices, S-lobe, etc.
• Coloring - definition of chromatic number χ(G), Proposition 5.1.7 χ(G) >= n(G)/α(G), χ(G) <= Δ(G) + 1 (Proposition 6.1.3), 6-color theorem and 5-color theorem (Theorem 6.3.1)
• Hamiltonian cycles and Dirac's Theorem (7.2.8)

Test topics - these are the topics covered on exams 1, 2, 3 and 4. Any of these may appear on the exam

• 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).
• Cayley's formula (Theorem 2.2.3) and Prüfer codes
• 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)
• Connectivity, edge-connectivity and associated definitions: separating set, k-connected, connectivity of a graph, disconnecting set, edge connectivity, edge cut, etc.
• Equivalence of a minimal disconnecting and an edge cut,
• (Theorem 4.1.9) κ(G) <= κ'(G) ≤ δ(G)
• Theorem 4.1.11 "if G is 3-regular κ(G) = κ'(G)"
• Theorem 4.2.8 (Ear-Decomposition Theorem)
• Menger's Theorem - and variants and Fan-Lemma
• Lemma 6.2.9 (Every 3-connected graph G with at most 5 vertices has an edge e such that G.e is 3-connected)
• 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 of a cut,
• Lemma 4.3.5
• Lemma 4.3.7
• Corollary 4.3.8 (Weak Duality)
• Algorithm 4.3.9 (Ford-Fulkerson labeling algorithm)
• Theorem 4.3.11 (Max-flow min-cut Theorem - Ford - Fulkerson),
• Definitions: Planar graphs, plane graphs
• Euler's Formula,
• Definition: Dual Graph,
• Proposition 6.1.13 (if G is a plane graph, then 2e(G) is the sum of the lengths of the faces of G), outerface, outerplanar
• Theorem 6.1.23 (If G is a simple planar graph then e(G) ≤ 3n(G) - 6 if G is also triangle-free e(G) ≤ 2n(G) - 4.
• Proposition 6.1.26 (Equivalence of the following three statements when G is a simple n-vertex plane graph: G has 3n(G) -6 edges. G is a triangulation. G is maximal plane graph)