Math 485: Graph Theory

Outline of Topics for Midterm Exam

Stephen G. Simpson

November 2, 2009

The midterm exam will include material from the following sections in the West textbook: 1.1, 1.2, 1.3, 1.4, 2.1, 2.2, 2.3, 3.1, 3.2.

1.1. basic concepts (a) vertices, edges

(b) loops, multiple edges

(c) simple graphs, non-simple graphs

(d) the adjacency matrix

(e) the incidence matrix

(f) isomorphism, isomorphic graphs

(g) the complete graph K_{n}

(h) the complete bipartite graph K_{mn}

(i) the Petersen graph

(j) the n-cube

(k) the n-wheel, the n-ladder, etc. 1.2. connectivity

(a) walks, trails, paths, cycles, distance

(b) connected components, diameter

(c) cut edges

(d) k-connected graphs, Menger’s theorem

(e) cut vertices, nonseparable graphs, blocks

(f) bipartite graphs

(g) bipartite graphs and odd cycles

(h) Euler trails

(i) Euler’s theorem 1.3. degrees and counting

(a) the degree of a vertex

(b) the degree sum formula, ∑ d_{i} = 2m

(c) r-regular simple graphs

(d) induction

(e) counting cycles, etc. 1.4. directed graphs

(a) walks, trails, paths, cycles

(b) in-degree, out-degree

(c) the degree sum formula for digraphs

(d) adjacency matrix, incidence matrix

(e) weak components, strong components

(f) Euler’s theorem for digraphs

(g) positional games, kernels

(h) directed acyclic graphs

(i) DeBruijn cycles 2.1. trees

(a) acyclic graphs

(b) the formula e = n − 1

(c) cut edges, components

(d) spanning trees

(e) the tree graph, T versus T − e + e′ 2.2. enumeration of spanning trees

(a) the recursion formula τ(G) = τ(G − e) + τ(G · e)

(b) the double edge formula

(c) solving recursion formulas

(d) spanning trees in the n-wheel, the n-ladder, etc.

(e) the matrix tree theorem

(f) spanning trees in K_{n}, K_{mn}, etc. 2.3. optimization and trees

(a) weighted graphs

(b) minimum-weight spanning trees

(c) Kruskal’s algorithm (d) minimum weight uv-paths

(e) Dijkstra’s algorithm

(f) examples 3.1. matchings and coverings

(a) matchings

(b) perfect matchings

(c) maximum matchings

(d) M-augmenting paths

(e) Berge’s theorem

(f) matchings in bipartite graphs

(g) the neighborhood of a set of vertices (h) Hall’s theorem

(i) the marriage theorem

(j) vertex coverings

(k) minimum vertex coverings

(l) the König-Egerváry theorem

(m) bipartite graphs and 0-1 matrices 3.2. algorithms and matchings

(a) the assignment problem

(b) the augmenting path algorithm

(c) weighted matchings

(d) the weighted assignment problem (e) weighted coverings

(f) the Hungarian algorithm