The final exam covers the entire semester’s work—see also the Exam 1 Topics and Exam 2 Topics pages.

The graph theory topics listed below constitute the material since Exam 2. They are covered in:

• in-class material and handouts;
• Homework Sets 7–9;
• on-line notes (Euler’sTheorem&CycleLemma, SpanningTreeMethods);
• on-line notebooks (Graphs, AdjacencyMatrix&Walks, WalksInK33, GrayCode, KuratowskiExamples); and
• text sections 7.1–7.3, 8.1–8.2, 12.2, 13.2–13.3

The graph theory topics include:

• Basic terminology: vertices, edges, loops, adjacent vertices, edge incident to vertex, etc.
• Examples of special graphs and special types of graphs, including regular graphs, complete graphs, complete bipartite graphs, and (hyper)cube graphs.
• Degrees of vertices; Handshaking Theorem
• Subgraphs, joins
• Isomorphic graphs; invariants of isomorphic graphs (including degree structure, connectedness)
• Walks, trails, paths; closed walks, closed trails, cycles
• Eulerian and Hamiltonian graphs: definitions, theorems about necessary and/or sufficient conditions (Euler’s Theorem, Dirac and Ore’s Theorems); Gray code as giving Hamiltonian cycle in hypercube.
• Directed graphs
• Adjacency matrix and meaning of its matrix powers
• Trees: definition, spanning tree of a connected graph and methods for finding such (cutting-down method; depth-fist search method)
• Vertex coloring, chromatic number, Brookes’s Theorem, greedy algorithm for finding vertex coloring

Not covered on the exam are map-coloring and Euler’s Formula f  − e + v = 2.