Section B

1. Let G and H be two graphs on the same set V of vertices.

Let [G]_H be the number of those permutations a of V such that if {u,v} is an edge in E(H) then {a(u),a(v)} is an edge in E(G).

For X Í E(H), let [G]_H\X be the number of those permutations a of V such that if {u,v} is an edge in E(H)-X then {a(u),a(v)} is also an edge in E(G) but if {u,v} is in X then {a(u),a(v)} is not in E(G).

Starting from the formula

Hence show that if n = |V| and m = |E(G)| and if either m > n(n-1)/4 or m > 1+ lgn! then G is edge-reconstructible.

Suppose |V(G)| > 16. Show that either G or its complement [`(G)] is edge-reconstructible.

2. (a) Let G be a graph without isolated vertices and let H be a subgroup of Aut(G). Show that if the action induced by H is transitive on the edges of G but not on its vertices then G is bipartite.

(b)  Let G be a graph and suppose H is a subgroup of Aut(G) whose action is transitive on the vertices and the edges of G. Suppose also that the action of H is not symmetric on the edges of G. (The action of H is symmetric on the edges of G if, for any two edges {a,b}, {c,d}, there exist a, b Î H such that a(a) = c, a(b) = d and b(a) = d, b(b) = c.)

With each 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 group H induces the natural action on the set of arcs defined by

Let s = (s₁,s₂) be an arc of G, and let D be a digraph whose vertex-set is V(G) and whose arc-set is the orbit of s under the action of H. Prove that

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

(d)  Deduce that if G is a graph on at least four vertices which is edge-transitive and not bipartite, and whose vertices have odd degree then the line-graph K = L(G) is a vertex-transitive graph which is not a Cayley graph.

[You may assume the following results:

• If K is a Cayley graph then there is a subgraph of Aut(G) which acts regularly on V(K).
• Whitney's result which says that, for graphs on more than four vertices, any edge-automorphism is induced by an automorphism.]

3. Let G be a group and let H,K be two subgroups of G. Let S be a subset of G. Define the graph Cos(G,H,K,S) to be the bipartite graph whose vertices are the left cosets of H and of K, where two cosets aH and bK are adjacent if and only if b^-1a Î KSH.

Let G be a graph whose vertex-set is partitioned into two orbits V₁, V₂ under the action of G = Aut(G), and let u Î V₁ and v Î V₂. Let H be the stabiliser of the vertex u and K the stabiliser of the vertex v. Let S be the set of all those permutations p Î G such that p(u) is adjacent to v. Show that:

• Define f:V(Cos(G,H,K,S))® V(G) by f(aH) = a(u) and f(bK) = b(v). Show that f is an isomorphism and deduce that G is isomorphic to Cos(G,H,K,S).
  

• Show that l_t is an automorphism of F.
• Let {a₁H,b₁K} and {a₂H,b₂K} be two edges, therefore a₁ = b₁k₁h₁ and a₂ = b₂k₂h₂ where h_i Î H and k_i Î K, (i = 1, 2). Let t = a₂ h₂^-1h₁a₁^-1. By considering l_t, show that F is edge-transitive.