Math 485, Graph Theory: Midterm Exam

Stephen G. Simpson Monday, November 9, 2009 Solutions

1. (a) If G is a k-regular graph with n vertices, how many edges does G have? Solution. kn/2, by the degree-sum formula.

(b) Draw a 3-regular graph with 11 vertices or prove that no such graph exists. Solution. Part (a) implies that no such graph exists, because in this case kn/2 = 3 · 11/2 which is not an integer.

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

Solution. The answer is 48. To see this, pick a vertex v of the 3-cube, and let e_{1}, e_{2}, e_{3} be the edges which are incident to v. An automorphism must carry v to some vertex v′. There are 8 choices for v′. Once v has been chosen, there are 3! = 6 choices for mapping e_{1}, e_{2}, e_{3} to the edges e′_{1}, e′_{2}, e′_{3} which are incident to v′. Once these 8 · 6 = 48 choices have been made, the automorphism is completely determined.

3. True or false.

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

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

(c) Every connected bipartite graph contains a cycle of even length. False. For instance, K_{1,1} or K_{1,2}.

(d) The Petersen graph has 25 edges. False.

(e) A weakly connected digraph with deg^{+}(v) = deg^{−}(v) for all vertices v is strongly connected. True. (This is implicit in Euler’s Theorem for digraphs.)

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

Solution. The Matrix Tree Theorem tells us that

τ(K_{4}) = | \begin{matrix}3 & −1 & −1 \\ −1 & 3 & −1 \\ −1 & −1 & 3 \end{matrix} | = 16.

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 twoperson positional game starting at u. Under what conditions does the first player have a winning strategy?

Solution. The first player has a winning strategy under either of the following circumstances:

(a) At least one of the uv-paths is even, and at least one of the vw-paths is odd.

(b) At least one of the uv-paths is odd, and all of the vw-paths are even.

Otherwise, the second player has 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.

Solution. We reason probabilistically. Let e be a randomly chosen edge of K_{n}, and let T be a randomly chosen spanning tree of K_{n}. The probability that e belongs to T is the number of edges in T divided by the total number of edges. In other words, (n − 1)/(n choose 2), which simplifies to 2/n. Therefore, the probability that e does not belong to T is 1 − 2/n. Therefore, the number of spanning trees not containing e is n^{n−2}(1−2/n) which simplifies to n^{n−3}(n − 2).

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}}.

Solution.

(a) The recursion

ϕ_{n} = ϕ_{n−1} + ϕ_{n−2}

holds for all n ≥ 3. It also holds for n = 2 if we define ϕ_{0} = 0.

(b) The characteristic equation is α^{2} = α + 1. The roots of this are α = (1 ± \sqrt{5})/2, so the general solution is

ϕ_{n} = A (\frac{1 + \sqrt{5}}{2})^{n} + B (\frac{1 − \sqrt{5}}{2})^{n} .

Using the initial conditions ϕ_{0} = 0 and ϕ_{1} = 1, we can solve for A and B to get A = 1/\sqrt{5}, B = −1/\sqrt{5}. Thus

ϕ_{n} = \frac{1}{\sqrt{5}} (\frac{1 + \sqrt{5}}{2})^{n} − \frac{1}{\sqrt{5}} (\frac{1 − \sqrt{5}}{2})^{n}

and this is our explicit formula.

(c) Since \frac{1 + \sqrt{5}}{2} > 1 > |\frac{1 − \sqrt{5}}{2}|, the term involving (\frac{1 − \sqrt{5}}{2})^{n} is

negligible for large n. Thus ϕ_{n} ≈ \frac{1}{\sqrt{5}} (\frac{1 + \sqrt{5}}{2})^{n} and in particular

lim_{n→∞} \frac{ϕ_{n+1}}{ϕ_{n}} = \frac{1 + \sqrt{5}}{2}.

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.

Solution. We omit the steps of the Hungarian algorithm. There are several maximum-weight matchings. One of them is M = {x_{1}y_{3}, x_{2}y_{2}, x_{3}y_{1}, x_{4}y_{4}} for a total weight of 3 + 2 + 4 + 4 = 13. A minimum-cost covering is given by u_{1} = 2, u_{2} = u_{3} = 1, u_{4} = 2, v_{1} = 3, v_{2} = v_{3} = 1, v_{4} = 2 for a total cost of 2 + 1 + 1 + 2 + 3 + 1 + 1 + 2 = 13.