Find the minimum spanning tree in each of the graphs below

Question

1. Are the following pairs of graphs isomorphic?

2. The double wheel D_n is constructed by taking the cycle C_n, then adding two new vertices u and v and edges from each of them to every vertex on the cycle. What is the degree sequence of D_n? How many vertices and edges does it have? Is D_n. connected?

3. Let G be a simple graph on 10 vertices and 38 edges. Prove that G contains K₄ as an induced subgraph.

4. (a) Find all the non-isomorphic graphs whose degree sequence is (6, 3, 3, 3, 3, 3, 3).

(b) Find a labeled tree whose Prufer code is (2, 3, 4, 4, 3, 2, 1, 6, 5).

5. (a) Find the minimum spanning tree in each of the graphs below using Kruskal's algorithm.

(b) Let G be a graph that is the union of a 2010-cycle and a 2011-cycle, with one common edge. Count the number of spanning trees of G.

6. (a) Find the number of 4-cycles in K_{2012, 2012}^.

(b)  Compute the diameter and radius of K_{2012, 2012}^.

(c)  Find the number of spanning trees of K_{2012, 2012}^.

7. The wheel graph W_n is defined as the join K₁ V C_n. How many spanning trees does W_n have for n ≥ 3?

8. (a) Find α(G), α'(G), β(G) and β'(G) for the bipartite graph below.

(b) Determine with proof whether the graph below has a perfect matching. If not, find the size of a maximum matching in that graph.

9. There are n children and n toys in a room. Each child wants to play with r specific toys, and for each toy, there are r children who want to play with that toy. Prove that we can organize r playing rounds so that in each of them, each child plays with a toy he/she wanted to, and no child plays with the same toy twice? (Contradicting real life a little bit, but not much, we assume that only one child can play with a toy at any one time.)

10. Alice and Bob play a game on a graph G alternately choosing distinct vertices. Alice starts by choosing any vertex. Each subsequent choice must be adjacent to the most recent choice of the other player. Thus, together they follow a path. The last player able to move wins. Who has a winning strategy that always works no matter how the other player plays?