1.  Let G be the graph whose vertices are the ordered pairs (x , y), where x , y e {0, 1, 2, 3}, and two vertices (x , y), (x′ , y′ ) are adjacent if and only if either x = x′  or y = y′ , but not both.

(a) Show that G is regular.

(b) Show that G is Hamiltonian.

(c) Show that G is vertex-transitive.

Check information:

(a) The graph is k-regular with k = 6.

(b)  One Hamiltonian cycle is given by starting at vertex (0, 0), going up to vertex

(0, 3), across to vertex (3, 3), down to vertex (3, 0) and then ‘snaking’ back via (2, 0), (2, 1), (2, 2), (1, 2), (1, 1), (1, 0) and finally back to (0, 0).

(c)  Omitted.

2.   (a)  Choose a labelling the tree T with the set of labels L = {1, 2, 3, 4, 5, 6, 7} and find the Pr¨ufer code for the resulting labelled tree.

(b)  Let L = {1, 2, 3, 4, 5}. Find the unique tree T labelled by elements of L such that its Pr¨ufer code is the sequence (2, 2, 3).

(c)  Let T be a tree. Let Q , R , S subtrees of T such that 

Show that 

Check information:

(a) We choose the labelling

The Pr¨ufer code is f(T) = (3, 1, 3, 2, 1).

(b) The required tree is

(c)  Omitted.

3.   (a)  Let G be the bipartite graph below, with bipartition X = {x1 , x2 , x3 , x4 , x5 } and Y = {y1 , y2 , y3 , y4 , y5 }. Find a maximum matching in G . Show that your maximum matching has the correct number of elements by exhibiting a minimum vertex cover

in G .

(b)  Let G be the bipartite graph below, with bipartition X = {x1 , x2 , x3 , x4 , x5 } and

Y = {y1 , y2 , y3 , y4 }.  Determine whether the graph  G  below has a matching of size IY I or not.

(c)  Let G be a bipartite graph with bipartition X , Y . Let M and N be matchings in G and let S S X , T S Y . Show that if every vertex in S is matched by M and every vertex in  T is matched by N, then there is a matching in G that matches every vertex in S u T

Check information:

(a) A  maximum  matching is  M  =  {x5y2 , x2y3 , x3y5 }.   A  minumum vertex cover is

{x3 , y3 , y2 }.

(b) There is no such matching.

(c)  Omitted.

4.   (a)  Let G be the graph below. Describe explicitly the block graph of G .

(b)  Let G be the graph below.  Find the connectivity K(G ) of G .  Determine whether

there are two vertices with more than K(G ) internally disjoint paths between them or not.

(c)  Let G be a connected graph with 3 blocks and k cut-vertices.  Find the possible values of k .

Check information:

(a) We have

(b) We have K(G ) = 3. Yes, there are two vertices with more than 3 internally disjoint paths between them.

(c) The only possible values for k are 1 and 2.

5.   (a)  Let G be the graph below.  Find the adjacency matrix and the Laplacian matrix

of G .

(b)  Determine how many connected strongly regular graphs there are with (k , λ , μ) =

(4, 1, 1).

(c)  Let G be a graph with V(G ) = {v1 , ... , ví }. Show that if G is k-regular and has m connected components, then the eigenvalue k of the eigenvector Jí  = (1, ... , 1) T of A  =  A(G )  has  multiplicity  m .   Hint:  you  may  rearrange the order of the vertices, since this does not change eigenvectors of the form Jí  = (1, ... , 1) T , their eigenvalues and multiplicities.

Check information:

(a) The required matrices are