Section B

1. (i) Let D be a finite set and G a group of permutations acting on D. A structure will be taken to mean a triple (D,G,w) where w is a function (colouring) from D to the set {0,1}. All notation for structures will have its usual meaning.

Let R and T be two structures and let X be a subset of D all of whose elements are coloured 1 in D. Prove that

Now suppose that R and T have the same structure-deck. Prove that

Deduce that, if R is not reconstructible from its structure-deck, and |X| is even, then |R®_X R| > 0.

Suppose P is a substructure of R with E(P) = m¢ < m = E(R), and suppose also that R is not reconstructible from its structure-deck. Deduce that

(ii) A necklace R is made up of N beads equally spaced out on a circular wire; m of these beads are coloured black, the rest are coloured white. The deck of R is the family of all necklaces obtained by changing, one at a time, the colour of each black bead into white.

Show that, if m > 5, then R is reconstructible from its deck.

[Hint: Consider, as a ``sub-necklace'' of R, the necklace P with N beads and only one of them coloured black.]

(iii) Let G be a graph on n ³ 10 vertices. Suppose G does not contain any induced subgraph isomorphic to the Petersen graph. Show that if G contains K₁₀ as a subgraph then G is edge-reconstructible.

(iv) Let k be a fixed but arbitrarily large positive integer. Describe briefly the key ideas in the construction of a graph G with k endvertices such that G is not reconstructible from its endvertex-deleted subgraphs.

2. (i) Show that a coset graph Cos(G, H, S) is vertex-transitive.

(ii) Let G be a vertex-transitive graph. Prove that G is isomorphic to some coset graph.

(iii) Consider the coset graph G = Cos(G,H,S) where S = {u,u^-1} for some s Î G-H. Show that G is also edge-transitive.

[Hint: Take any two edges e₁,e₂ of G. Show that there always exists a g Î G such that the left translation l_g: v® gv maps e₁ into e₂.]

(iv) Suppose that G is a vertex-transitive and edge-transitive graph, and let G = Aut(G). Prove that G is isomorphic to a coset graph Cos(G,H,S) where S can be taken to be a set {u,u^-1} for some u Î G-H.

[Hint: Let G be a coset graph as constructed in (ii), and let u,x Î S. Consider the edges {H,uH} and {H,xH}. Show that x = huk or x = hu^-1k, for some h,k Î H.]

3. (a) Let G be a Cayley graph Cay(G,S) and let f be an automorphism of the group G such that f(S) = S. Show that f, as a permutation of V(G) = G, is an automorphism of G fixing the vertex 1.

Now let G be a vertex-transitive graph and let G = Aut(G) be abelian. Prove that for any two vertices u,v of G there is an automorphism a in G such that a(u) = v and a(v) = u.

[You may assume that if G = Aut(G) acts regularly on V(G) then G is isomorphic to some Cayley graph of G. You may also assume that if G is an abelian group of permutations acting transitively on X, then G acts regularly on X.]

(b) Let G be a connected graph on p vertices, where p ³ 3 is prime. Suppose G is vertex-transitive. Show that G is Hamiltonian.

[Hint: Using the Orbit-Stabiliser Theorem, show that Aut(G) has an element a of order p. Let v₁ be a vertex of G and let v₂ be a neighbour of v₁. Then a or some power of a maps v₁ into v₂.]

(c) Let G be a finite group and H,K two subgroups of G such that HÇK = {1}. Let S = HÈK - {1}. Show that the Cayley graph G = Cay(G,S) is a line-graph.

[Hint: Use the Krausz characterisation of line-graphs. For any x Î G = V(G), consider the neighbours of x.]