4. Give a sketch of the proof of Frucht's Theorem:

If G is a finite group, then there exists a graph G such that Aut G @ G.

Let A_n be the alternating group acting on the set N = {1,2,...,n}. Show that there is no graph G with V(G) = N and such that the action of Aut G on V(G) is equivalent to that of A_n.

Give a 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.

It is required to construct two graphs G₁, G₂ with the following properties. Both graphs have endvertices; the set of endvertices in G_i is X_i. Moreover,

• The endvertices of G₁ are mutually pseudosimilar.
• The graph G₂ is not reconstructible from the collection of subgraphs G₂-v, v Î X₂.

For only one of the two graphs G₁, G₂, explain how, with the aid of Bouwer's Theorem, the graph G_i can be constructed if it is possible to construct a permutation group G_i acting on X_i and satisfying certain conditions. [You should state clearly what conditions G_i is supposed to satisfy, but you do not need to construct a specific example of a permutation group with these conditions.]

5. Let G be a finite group and S Í G such that S^-1 = S, 1\not Î S. Let the Cayley graph G(G,S) be defined by V(G(G,S)) = G and E(G(G,S)) = {{g,gs}: g Î G, s Î S}. Prove that G is isomorphic to a subgraph of Aut G(G,S) which acts regularly on V(G).

Show, by means of an example, that G need not be the full automorphism group of G(G, S).

From now on suppose that G is a vertex-transitive graph whose automorphism group Aut G acts regularly on V(G).

Prove that, for some S Í Aut G, G is isomorphic to the Cayley graph G(Aut G, S).

Now suppose also that |V(G)| is odd.

Prove that Aut G is not abelian.

Prove also that, if v is any vertex of G, then, in G-v, for any vertex w there is a vertex w¢ ¹ w such that w and w¢ are pseudosimilar in G-v.

6. (a) Let G be a graph on n vertices and m ³ n edges. In the sequel, for any graph H, s(H) denotes the number of subgraphs of G isomorphic to H. Let C_t denote the cycle on t vertices. Prove that

Deduce that s(C_n) is reconstructible from the deck of vertex-deleted subgraphs of G.

Indicate very briefly how this result gives that the characteristic polynomial of G is reconstructible.

[Kelly's Lemma may be used without proof.]

(b) Let G be a vertex-transitive and edge-transitive graph. Suppose also that G is not symmetric. (G is said to be symmetric if, for any two edges {a,b}, {c,d}, there exist a, b Î Aut G such that a(a) = c, a(b) = d and b(a) = d, b(b) = c.)

With every edge {a,b} we associate two ordered pairs (a,b) and (b,a) which we call arcs. If the arc (a,b) is denoted by t then (b,a) is denoted by t^-1. The automorphism group Aut G induces an action on the set of arcs by

Let t be an arc, and let D be a digraph whose vertex-set is V(G) and whose arc-set is the orbit of t under the action of Aut G. Prove that

• For every edge {a,b} of G, D contains exactly one of the arcs (a,b), (b,a).
• Aut G £ Aut D.
• D is vertex-transitive.
• The degree (valency) of G is even.