Math 485, Graph Theory: Final Exam

Stephen G. Simpson

Monday, December 14, 2009

13 problems, 220 points

1. (15 points) Draw a simple connected planar graph which is 6-regular, or prove that no such graph exists.

2. (15 points) Exhibit a planar graph G which has at least two different (nonisomorphic) dual graphs – depending on the planar representation of G. Exhibit two planar representations of G with different dual graphs. Make your G as small as possible.

3. (15 points) Draw a connected graph G consisting of three blocks which are isomorphic to K_{5} and K_{3,3} and C_{10} respectively. How many spanning trees does G have?

4. (15 points) State the Graph Minor Theorem. Use it to prove that graphs of genus ≤ g can be characterized by a finite list of forbidden minors.

5. (20 points) Recall that the octahedron is a simple connected 4-regular planar graph whose dual is simple and 3-regular. Recall that, according to Fáry’s Theorem, any simple planar graph has a straight-line representation.

(a) Draw a straight-line representation of the octahedron.

(b) Write a determinant for the number of spanning trees of the octahedron.

6. (20 points) True or False.

(a) τ(G) ≥ χ(G) for any graph G.

(b) Any graph of genus ≤ 3 is 9-colorable.

(c) A simple graph of genus ≤ 3 with n vertices has ≤ 3n + 12 edges.

(d) For k > 0, any k-regular simple graph has a perfect matching.

(e) In a tree, every edge is a cut edge.

7. (20 points) Use Heawood’s formula to find a lower bound for the genus of K_{12}, the complete graph on 12 vertices.

8. (15 points) Recall that L_{n} is the n-ladder, with 2n vertices. What is the diameter of L_{n}? What is the chromatic number of L_{n}? What is the genus of L_{n}? How many spanning trees does L_{n} have?

9. (20 points) Let G be a planar bipartite graph. Prove that the dual graph G^{∗} is Eulerian.

10. (15 points) Draw a graph G such that the number of spanning trees of G is given by the determinant

| \begin{matrix}3 & −2 & 0 & −1 \\ −2 & 6 & −2 & −1 \\ 0 & −2 & 3 & 0 \\ −1 & −1 & 0 & 4 \end{matrix} |

11. (15 points) Let G be a graph with n vertices. Recall that τ(G) is the number of spanning trees of G. Let G_{k} be the graph obtained from G upon replacing each edge by k parallel edges. What is the relationship between τ(G) and τ(G_{k})? Justify your answer.

12. (15 points) Let G be a connected graph with exactly n vertices and m edges. If G contains exactly two cycles, what can you say about the relationship between n and m? Justify your answer.

13. (20 points) Consider a weighted bipartite graph where the weights are given by the following matrix.

4 2 1
5 2 1
6 7 1

(a) By inspection, find a matching M of maximum weight. (You are not required to use the Hungarian algorithm.)

(b) Find a weighted vertex covering C of minimum weight.

(c) What relationship must hold between M and C?