Question 1

(a)  Find the number of distinct labelled simple graphs with 5 vertices.                [3 marks]

(b)  Show that only one of the following is the degree sequence of a graph, and construct a simple graph which has that degree sequence.

(i)  6, 5, 5, 4, 2, 2, 1,          (ii)  5, 3, 2, 2, 2, 2 .

[5 marks]

(c)    (i)  Give  all the  integers  n  (if there  are  any) for which the complete graph  Kn   is bipartite. Justify your answer.                                                                  [2 marks]

(ii)  G is a bipartite simple graph.  Show that its complement G is a connected graph

if and only if G is not a complete bipartite graph Kr,s .                           [6 marks]

(d)  G is a graph with n vertices and m edges. k is the smallest integer such that k ≥ 2m

Show that G has a vertex whose degree is at least k .                                    [4 marks]

Question 2

(a)  G is an r-regular simple graph with 2r − 1 vertices. Show that G is Hamiltonian.

[4 marks]

(b)  Consider a labelled tree T with Prüfer sequence 5, 3, 4, 6, 6, 2 .

(i)  Draw T .                                                                                                    [4 marks]

(ii)  Find the number of labelled trees with the same number of vertices as T .

[2 marks]

(c)  G is a connected simple graph. You are given that G is 2-connected, i.e. any separating set in G consists of at least two vertices.

Suppose two cycles C and C′  in G  have the same length e.  In each of the following cases, show that there is a cycle in G of length greater than e .

(i) C and C′  have exactly one vertex in common.                                        [6 marks]

(ii) C and C′  have no vertices in common. You may assume Menger’s theorem.

[4 marks]

Question 3

(a)  Show that the graph drawn below is not a planar graph.                                [6 marks]

(b) The chromatic number χ(G) of a graph G is the smallest number of colours that can be assigned to the vertices of G so that no two adjacent vertices have the same colour.

(i)  Identify the types of graph for which χ(G) ≤ 2 .                                     [2 marks]

(ii)  Suppose G  is simple and contains exactly one cycle of odd length.   Show that

χ(G) = 3 .                                                                                                 [5 marks]

(c)  Six chemicals A, B, C, D, E and F are to be stored in different areas of a laboratory. The following pairs must not be stored together:

(A, C), (A, E), (A, F), (B, C), (B, D), (B, E), (D, E) .

(i)  Express this as a graph theoretic problem and find the associated chromatic poly- nomial                                                                                                       [5 marks]

(ii)  Find the smallest number of areas needed, and the number of ways of storing the

chemicals in those areas.                                                                          [2 marks]

You may assume the following chromatic polynomials:

For a cycle Cn  of length n ,   PCn(k) = (k − 1)n + ( − 1)n (k − 1) . For any tree Tn  with n vertices,   PTn (k) = k(k − 1)n 一l .

Question 4

╱  、

(i)  Make a drawing of G .                                                                              [3 marks]

(ii)  Give a reason why 0 is an eigenvalue of L(G) and state its multiplicity, with a brief reason.                                                                                                      [3 marks]

(iii)  λl  is the largest eigenvalue of the adjacency matrix of G.  Use results from the

module to show that 1 ≤ λl  ≤ 3 .                                                            [3 marks]

(iv)  State the dimensions of the incidence matrix B of G.  Regarding B as a matrix

over 匹2 , give its rank and nullity.                                                             [3 marks]

(b)  G is a connected simple graph with adjacency matrix A .

(i)  Show that if A is the incidence matrix of some simple graph then G  is a cycle graph.                                                                                                       [4 marks]

(ii)  If G  is a cycle graph,  is A necessarily the incidence matrix of a simple graph?

Justify your answer.                                                                                  [4 marks]