Test topics - these are the topics covered on exams 1, 2 and 3. 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)