MAS1003 Discrete Mathematics: Problem sheet 5 Please refer to the graphs drawn overleaf

1. [2] Are the graphs G_{1} (the Petersen graph) and G_{2} isomorphic?

2. (i) [2] Find two graphs, each with six vertices and each regular with valency 2, which are not isomorphic. (ii) [4] Find two connected graphs, each with eight vertices and each regular with valency 3, which are not isomorphic.

3. [2] Show that the Petersen graph has no cycle with fewer than five edges.

4. Which of the following graphs are Hamiltonian?

(i) [1] the complete graph K_{n}; (ii) [3] the complete bipartite graph K_{r,s}; (iii) [4] the Petersen graph; (iv) [2] the cube graph (G_{3}).

If so find a Hamiltonian cycle. If not give reasons.

5. [2] Find an Eulerian walk in G_{4}.

6. [3] Show that each tree with more than one vertex has at least two vertices of valency 1. [Hint: use the handshaking lemma.]

7. [3] Find all trees on six vertices, up to isomorphism.

8. [2] Find the Prüfer codes of the labelled trees T_{1}, T_{2} and T_{3}. Check by reconstructing the trees from the codes.

9. [2] Find the labelled trees with the Prüfer codes

(i) (4, 2, 7, 2, 7, 1); (ii) (3, 1, 6, 8, 8, 3, 2, 1); (iii) (10, 1, 9, 3, 4, 7, 10, 3, 11, 1).

Check by obtaining the Prüfer codes from the trees.

10. For which values of r and s is the complete bipartite graph K_{r,s} planar? Give reasons.

11. Are the following graphs planar?

(i) [2] the cube graph; (ii) [4] the Petersen graph; (iii) [2] G_{5}.

If so draw the graph without crossings. If not give reasons.

12. Give colourings of the following graphs, using as few colours as possible:

(i) [2] the cube graph; (ii) [2] G_{5}; (iii) [4] the Petersen graph.

RJC 30/11/1999