Question 1

(a)  For each of the following, either give an example or explain why none exists.

(i) A self-complementary graph with 4 vertices.

(ii) A self-complementary graph with 6 vertices.

(iii) A non-planar graph with chromatic number 2.

(iv) A planar graph with chromatic number 4.

(b) A connected, simple, graph G has degree sequence 5, 5, 4, 3, 3, 2, 2, 2

(i)  Show that G must be planar.                                                                   [3 marks]

(ii)  Find the number of edges and faces in a plane drawing of G .                [2 marks]

(c)  Consider the complete bipartite graphs Kr,s .

(i)  Show that a necessary condition for Kr,s  to be Hamiltonian is that r + s is even. Is this condition also sufficient?  Make sure that you fully explain your answer.

[3 marks]

(ii)  Explain which simple connected graphs G contain K1 ,2  as a subgraph.   [2 marks]

(iii)  Explain which simple connected graphs G contain K1 ,2  as an induced subgraph.

[2 marks]

Question 2

(a)  Find the Prüfer sequence for the tree drawn below                                         [4 marks]

(b) A sequence of integers, S, consists of p repeats of the sequence k, k _ 1, . . . 1, where p, k  ∈ 肠+   and p  ≥ 1,  k  >  1 .   For example, for p = 3 and k = 2 the sequence is 2, 1, 2, 1, 2, 1 .

(i)  Show that for all values of p ≥ 1 and all values of k > 1, S is a Prüfer sequence.

[3 marks]

(ii)  For k = 3 and arbitrary p, what is the degree sequence of the associated tree?

Your expression will depend on p .  Explain your answer.                          [3 marks]

(c)  Students take one of two degrees:  Mathematics or Mathematics with Music.

Mathematics students take the four  modules  linear algebra, classical dynamics,  real analysis and vector calculus.

Mathematics with Music students take linear algebra, vector calculus and music.

Exams of the same length are to be scheduled for each subject and it is required that there are no exam clashes.

(i)  Explain how to frame the problem as a graph theoretic colouring problem, drawing an appropriate graph, G .                                                                          [2 marks]

(ii)  Derive the chromatic polynomial for your graph G .                                [5 marks]

(iii)  Hence find the number of time slots needed and the number of possible arrange-

ments for the exams.  Explain clearly your working.                                 [3 marks] You may use the following formula.  For a graph G with chromatic polynomial PG (k),

PG (k) = PG ↓ e (k) _ PG\e(k) .

A tree Tn  with n vertices has chromatic polynomial

PTn (k) = k(k _ 1)n ↓ 1 .

A cycle graph Cn  with n ≥ 3 vertices has chromatic polynomial

PCn(k) = (k _ 1)n + (_1)n (k _ 1) .

Any other formula you use must be derived.

Question 3

(a)  Consider the flow from P to Q in the network shown below, where the numbers indicate the capacities of the arcs.

(i)  Find the maximum flow. Justify your answer.                                         [3 marks]

(ii)  Draw a diagram illustrating one way that the maximum flow can be achieved.

[2 marks]

(b)  In a large house there are six rooms, labelled 1 to 6, available to let and six students,

Amy, Beth, Callum, Dan, Ed, Freya seeking accommodation.  Amy likes rooms 1 and 3.  Beth likes rooms 2, 3, 4 and 5.  Callum likes rooms 1 and 6.  Dan likes rooms 2, 5 and 6.  Ed likes room 3 and 6.  Freya likes rooms 1, 3 and 6.

Does a matching of students to rooms exist that suits everyone?  Justify your answer using Hall’s theorem.                                                                                        [4 marks]

(c)  Let G be a simple graph with 10 vertices such that both G and its complement G are planar. Show that G must have the following properties:

(i)  If m is the number of edges of G , then 21 ≤ m ≤ 24 .                            [4 marks]

(ii)  G has a vertex with degree at least 5 .                                                     [3 marks]

(iii)  If X = 6v1 , v2 , v3 , v4 , v5 ì is a set of neighbours of a vertex v in G , then the number

of edges of G with both ends in X is at most 7 .                                     [4 marks]

Question 4

(a)  G1  and G2  are the following undirected labelled graphs.

(i) Write down the adjacency matrix A(Gi ) of each graph, relative to the orderings of the labels shown.                                                                                      [5 marks]

(ii)  Show that if  ．(╱)  ．(、)  is an eigenvector of A(G1 ) then          is an eigenvector

of A(G2 ) .                                                                                                  [5 marks]

(iii) What are the diagonal entries of A(G2 )2k+1  for all positive integers k?   Explain your answer.                                                                                             [3 marks]

(b)  G is a connected simple graph with n ≥ 3 vertices and m edges.  Let v be any vertex of G and let mJ  be the number of edges of G _ v .

Show that mJ = m _ d(v) and that mJ  ≤  . Deduce that if m > 

then G is Hamiltonian.                                                                                         [7 marks]