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.

• k-coloring, color class, k-colorable, k-critical, χ(G), ω(G)
• 5.1.7 (χ(G) >= ω(G) and χ(G) >= n(G)/α(G)),
• Cartesian product (5.1.11),
• Greedy Coloring, 5.1.13 χ(G) <= Δ(G) + 1, 5.1.14,
• 5.1.18 (if G is k-critical, then δ(G) >= k - 1), 5.1.19
• Brooks' Theorem 5.1.22
• Mycielski's construction, 5.2.3
• Turán's Theorem, 5.2.8 and 5.2.9,
• Chromatic polynomial, 5.3.3 (If T is a tree, then χ(T; k) = k(k-1)^n), 5.3.4, Chromatic recurrence 5.3.6
Planar graphs, plane graphs, Drawings, 6.1.2 (K_5 and K_{3,3} are not planar), Dual graph, 6.1.3 (sum of face length equals two times the number of edges),
• 6.1.21 Euler's Formula, 6.1.23 (G planar and n(G) >= 3 implies e(G) <= 3n(G) - 6) 6.1.26 (characterization of maximal planar graphs)
• subdivision, Kuratowski's Theorem, Every simple planar graph is 6-colorable 6.3.1. (5-color theorem) Every simple graph is 5-colorable,
• Edge coloring, k-edge coloring, k-edge colorable, proper edge coloring, edge chromatic number, chromatic index, Vizing's Theorem (If G simple, then χ'(G) <= Δ(G) + 1), The chromatic index of the Petersen graph is 4.
• Full Vizing's Theorem (χ'(G) <= Δ(G) + μ(G)) 1-factorization, 1-factorable, If G is a k-regular bigraph, then G is 1-factorable, (7.1.7) If G is bipartite, then χ'(G) = Δ(G).
• Hamlitonian cycles, Hamilonian graphs, K_{m,n} is hamiltonian iff m=n >= 2, If G is a Hamiltonian bipartite graph, then the parts have the same size, The Petersen graph is not Hamiltonian, c(H)=number of components of H, G Hamiltonian implies c(G-S) <= |S| for every non-empty S a subset of V(G).

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