4. (a) Let G be a finite group. Describe how a graph G can be constructed such that Aut(G) is isomorphic to G.

Give an example of a permutation group G acting on a set X such that there is no graph G for which the action of Aut(G) on V(G) is equivalent to the action of G on X. [9]

(b) Give a short sketch of the proof of Bouwer's Theorem:

Let G be a group of permutations acting on the set X. Then there exists a graph G such that X Í V(G), Aut (G) @ G, X is invariant under the action of Aut (G), and the action of Aut (G) on X is equivalent to that of G.

[9]

(c) Let F = {0,1} be the binary field and let X be the k-dimensional vector space consisting of all k-tuples of elements of G. Let G be the group of permutations consisting of all linear transformations on X. Let A be a basis of X and let B be a set of k vectors of X whose sum is the zero vector but such that any proper subset of B is linearly independent.

Show that there is no a Î G such that a(A) = B but that, given any two proper subsets A¢ Ì A, B¢ Ì B with the same number of vectors, there is a Î G such that a(A¢) = B. [8]

(d) Use the result in (c) and Bouwer's Theorem to show how to construct, for any k, two non-isomorphic graphs H, K each with exactly k endvertices and having the same endvertex-deck. [8]

5. Let G be a group, S Í G such that S^-1 = S, and G the Cayley graph Cay(G,S).

(a) Let a Î G. Show that the permutation l_a:x® ax of G is an automorphism of the graph G. [8]

(b) Let f be an automorphism of the group G such that f(S) = S. Show that f is an automorphism of the graph G fixing the vertex 1. [8]

(c) Suppose that G is a graphical representation (GRR) of the group G. Show that if G is abelian, then it is an elementary abelian 2-group. [8]

(d) Again, let G = Cay(G,S) be a GRR of G. Let T be another subset of G with T^-1 = T, and let H = Cay(G,T). Suppose s is an isomorphism from the graph G to the graph H such that s(1) = 1. Show that:

• For any a Î G,

  s-1ls(a)-1sla

  is an automorphism of the graph G;
• For any a Î G,

  s-1ls(a)-1sla = id,

  where id is the identity permutation;
• For any a,b Î G, s(ab) = s(a)s(b);
• s is an automorphism of the group G such that s(S) = T.

[10]

6. (a) Let G be a graph on at least three vertices. Prove that each of the following is reconstructible from the deck D(G):

• The number of edges of G;
• For any G-v Î D(G), the degree in G of the missing vertex v;
• For any G-v Î D(G), the degrees of the neighbours of v in G.

[9]

(b) Show that the complete bipartite graph K_p,q other than K_1,1 is reconstructible. [7]

(c) Let G have a unique vertex v₀ of degree k and suppose that G contains no vertex of degree k-1. Suppose also that no two neighbours of v₀ are similar in G-v₀. Show that,

• The condition on the degree of v₀ is recognisable from D(G);
• The graph G-v₀ and the graphs G-w, for all neighbours w of v₀, are identifiable from D(G);
• If w is a neighbour of v₀, then the vertex v₀ is identifiable in G-w;
• Given any G-w with w neighbour of v₀, there is a unique vertex w¢ in G-v₀ and a unique vertex v¢ in G-w such that G-v₀-w¢ @ G-w-v¢.

Deduce that the neighbours of v in G are identifiable in G-v and hence that G is reconstructible. [9]

(d) Let G and H be two graphs on the same set V of vertices. For each X Í E(G), let [H]_G\X be the number of permutations a of V such that if {u,v} is an edge in E(G)-X then {a(u),a(v)} is also an edge in E(H), but if {u,v} is in X then {a(u),a(v)} is not in E(H). Let [H]_G be [H]_G\X with X = Æ.

Starting from the Nash-Williams Formula

Deduce that if a Hamiltonian graph on m edges and n vertices contains r Hamiltonian paths, and