1.  The graph G is given by the picture

1         2  

9                                11

(a)  Explain why the transposition f = (5, 7) (swapping the vertices 5 and 7 and

leaving all the other vertices   xed) and the product of transpositions g = (1, 3)(4, 8)(9, 11) de  ne isomorphisms of G with itself.

Solution:  [1 mark] Each of the permutations f and g of the vertex set    V = {1, 2, . . . , 11} has the property that two vertices x and y are adjacent if and only if their images under f and g are adjacent. Indeed, by replacing the vertices with their respective images under the bijections f and g we get

1         2              3

4         7        6               5         8 

9                                11

and

3         2              1

8         5        6               7         4 

11                               9

{2, 4, 6, 8, 10}.  For the same reason, if both v and w belong to the same subset {5, 7} or {1, 3, 9, 11}, then the new graph is not Hamiltonian either. By taking into account the symmetries given in part  (a), we   nd that it suces to consider the cases v  ∈  {1, 9} and w  =  5 and then apply the isomorphisms.

Both graphs G + {1, 5} and G + {9, 5} turn out to be Hamiltonian with the respective spanning cycles given by

G + {1, 5} :       5, 1, 4, 9, 6, 3, 8, 11, 10, 7, 2, 5, G + {9, 5} :       5, 9, 4, 1, 6, 3, 8, 11, 10, 7, 2, 5.

Thus, applying the isomorphisms of part (a), we conclude that the complete list consists of the eight pairs

{1, 5},    {1, 7},    {3, 5},    {3, 7},    {9, 5},    {9, 7},    {11, 5},    {11, 7}.

2.  Consider the trees with 7 vertices which have exactly 4 leaves.

(a)  Find a representative of each isomorphism class of such trees and explain why these representatives are pairwise non-isomorphic.

Solution:  [2 marks] The representatives are

The degree sequence of the   rst two trees is (1, 1, 1, 1, 2, 3, 3), whereas the two other trees have the degree sequence (1, 1, 1, 1, 2, 2, 4). Furthermore, the vertices of degree 3 are adjacent in the   rst graph but not in the second. The vertex of degree 4 is adjacent to three leaves in the third graph and only to two leaves in the fourth. This shows that all four trees are pairwise non-isomorphic.

(b)  Explain why any such tree is isomorphic to one of the representatives in the previous part.

Solution:  [2 marks] Label the leaves of such a tree by 1, 2, 3, 4 and the remaining vertices by 5, 6, 7.  If we delete all four leaves, then we are left with a tree with 3 vertices, which must be a path graph.  We may assume that its middle vertex is 6.  To list all isomorphism classes, we will look for all possible ways to connect 4 vertices 1, 2, 3, 4 with this path graph by 4 edges so that the resulting trees have exactly 4 leaves.  The last condition implies that we must use edges to connect each of the vertices 5 and 7 of the path graph with one of the leaves.  We may assume that the two edges are {1, 5} and {4, 7}. The remaining vertices 2 and 3 can be adjacent to the same vertex (5, 6 or 7) or they can be adjacent to two distinct vertices thus yielding one of the trees listed in the previous part.