1. Are the following pairs of graphs isomorphic?
![2090_Graph.png](https://secure.tutorsglobe.com/CMSImages/2090_Graph.png)
2. The double wheel Dn is constructed by taking the cycle Cn, 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 Dn? How many vertices and edges does it have? Is Dn. connected?
3. Let G be a simple graph on 10 vertices and 38 edges. Prove that G contains K4 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.
![150_Spanning Tree.png](https://secure.tutorsglobe.com/CMSImages/150_Spanning%20Tree.png)
(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 K2012, 2012.
(b) Compute the diameter and radius of K2012, 2012.
(c) Find the number of spanning trees of K2012, 2012.
7. The wheel graph Wn is defined as the join K1 V Cn. How many spanning trees does Wn have for n ≥ 3?
8. (a) Find α(G), α'(G), β(G) and β'(G) for the bipartite graph below.
![648_Bipartite Graph.png](https://secure.tutorsglobe.com/CMSImages/648_Bipartite%20Graph.png)
(b) Determine with proof whether the graph below has a perfect matching. If not, find the size of a maximum matching in that graph.
![178_Graph1.png](https://secure.tutorsglobe.com/CMSImages/178_Graph1.png)
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?