Math 485, Graph Theory: Midterm Exam Stephen G. Simpson Monday, November 9, 2009 8 problems

1. (a) If G is a k-regular graph with n vertices, how many edges does G have?

(b) Draw a 3-regular graph with 11 vertices or prove that no such graph exists.

2. Recall that Q_{3} is the 3-cube. How many automorphisms does Q_{3} have? Justify your answer.

3. True or false.

(a) The number of spanning trees in the n-cycle is n.

(b) Dijkstra’s algorithm applied to a connected weighted graph produces a minimum-weight spanning tree.

(c) Every connected bipartite graph contains a cycle of even length.

(d) The Petersen graph has 25 edges.

(e) A weakly connected digraph with deg^{+}(v) = deg^{−}(v) for all vertices v is strongly connected.

4. It is known that K_{4} has 16 spanning trees. Prove this using the Matrix Tree Theorem.

5. Let G be an acyclic digraph with vertices u, v, w consisting of k pairwise disjoint uv-paths plus l pairwise disjoint vw-paths. Consider the 2-person positional game starting at u. Under what conditions does the first player have a winning strategy?

6. It is known that K_{n} has n^{n−2} spanning trees. If e is an edge of K_{n}, how many spanning trees does K_{n} − e have? Justify your answer.

7. The Fibonacci numbers are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … where each number is obtained by adding the previous two numbers. Let ϕ_{n} be the nth Fibonacci number. Thus ϕ_{1} = 1, ϕ_{2} = 1, ϕ_{3} = 2, ϕ_{4} = 3, ϕ_{5} = 5, ϕ_{6} = 8, ϕ_{7} = 13, etc.

(a) Write a recursion formula for ϕ_{n}.

(b) Solve your recursion to obtain an explicit formula for ϕ_{n}.

(c) Find lim_{n→∞} \frac{ϕ_{n+1}}{ϕ_{n}}.

8. Consider a weighted bipartite graph with weights as indicated:

y_{1} y_{2} y_{3} y_{4}
x_{1} 4 3 3 3
x_{2} 4 2 2 2
x_{3} 4 1 1 1
x_{4} 4 1 3 4

Use the Hungarian algorithm to find a matching of maximum weight and a weighted covering of minimum cost. Show all of the intermediate steps, including weighted coverings and the equality subgraphs which are associated with them.