Answer all questions .  Carefully justify your answers .

1.   (a)  Describe (up to isomorphism) all bipartite graphs with 6 vertices and

8 edges. For each such graph describe a Hamilton cycle or explain why it does not contain one.

(b)  State Dirac’s theorem on the existence of Hamilton cycles.

(c)  For which integers 2 ≤ r ≤ n does the Tur´an graph Tr (n) contain a Hamilton cycle?

(d)  Let G be a graph of order n 司 3 containing a path of length n — 1: v1 v2．．．vn . Prove that if d(v1 )+d(vn ) 司 n then G contains a Hamilton cycle. (25 marks)

(a)  Up to isomorphism, the only bipartite graphs of order 6 and size 8 are K2 ,4  and K3 ,3  with an edge removed.  Since any Hamilton cycle in a bipartite graph must alternate between vertex classes K2 ,4  does not contain a Hamilton cycle.  However K3 ,3  with an edge removed does contain a Hamilton cycle.  Let V (K3 ,3 ) = {1, 2, 3} n {4, 5, 6} and 26 be the deleted edge then it contains the Hamilton cycle:  142536.  [7 marks]

(b) If G is a graph of order n  司 3 and δ(G)  司 n/2 then G contains a Hamilton cycle.  [3 marks]

(c)  For r = 2 we have T2 (n) = K「n/2| ,「n/2」  which is Hamiltonian iff n is even.  For r 司 3 we know that every vertex is adjacent to all vertices not in the same class and hence for 3 ≤ r 司 n

δ(Tr (n)) = n — ln/r」司 n/2.

Hence Dirac’s theorem implies that Tr (n) contains a Hamilton cycle for all 3 ≤ r ≤ n.  [5 marks]

(d) We can adapt the proof of Dirac’s theorem as follows.

If v1 vn   e E(G) then we clearly have a Hamilton cycle, so suppose this is not the case.   Let A = Γ(vn )/{vn -1 ) and B  =  {vi   | vi+1   e Γ(v1 )}/{v1 }.  If we show that A U B   9 then we are done since if vi  e A U B then v1 v2．．．vi vn vn -1．．．vi+1  is a Hamilton cycle.             Now A, B 三 {v2 , . . . , vn -2 } and |A|+|B| = d(vn ) — 1+d(v1 ) — 1 司 n — 2 and so by the pigeonhole principle AUB  9 and the proof is complete. [10 marks]

2.   (a)  Describe the Tur´an graph T3 (8).   For which 2  ≤ r  ≤ n does T3 (8) contain a copy of Tr (n)?

(b)  For a graph F and an integer n ≥ 1 let ex3 (n, F) be the maximum number of copies of K3  in an F-free graph of order n. Prove that the following limit exists:

ex3 (n, F)

n →o         ╱3(n)、     .

(c)  Prove that π3 (K4 ) ≥ 2/9. (25 marks)

(a) T3 (8) is the complete 3-partite graph with vertex classes of order 3,3,2. It cannot contain any Tr (n) with r > 3 or n > 8. By deleting vertices it is easy to see that it contains T3 (n) for 3 ≤ n ≤ 8.  For r = 2 it clearly contains T2 (n) for n = 2, 3, 4, 5, 6 (simply remove the smalled vertex class and then delete vertices). It also contains T2 (7): delete a vertex from the smallest class and remove edges from the remaining vertex in that class to one of the larger classes..  However it does not contain T2 (8) since any 2-colouring of T3 (8) must result in a pair of vertices from the same class in T3 (8) being given different colours and so the corresponding edge is missing.  [10 marks]

(b)  Let G be an F-free graph of order n with ex3 (n, F) copies of K3 .  If v  e V (G) then G/{v} contains at most ex3 (n 一 1, F) copies of K3 . Let t(H) denote the number of copies of K3  in a graph H . By double counting and using the fact that every K3  contains 3 vertices we have

(n 一 3)t(G) =            t(G/{v}) ≤ nex3 (n 一 1, F)

veV (G)

Thus (n 一 3)ex3 (n, F) ≤ nex3 (n 一 1, F) and hence

ex3 (n, F)      ex3 (n 一 1, F)

Thus the sequence is descreasing and bounded below (by zero) so con- verges.  [10 marks]

(c)  This follows by observing that T3 (n) is K4-free and contains「|「|「| copies of K3 . Hence

t3 (n)              「n/3|「(n + 1)/3|「(n + 2)/3|      6       2

3.   (a)  Give an example of an intersecting chain of maximum size in p([5]).  (b)  Give an example of an intersecting antichain of maximum size in p([5]).

(c)  State the LYM-inequality.

(d)  Let n ≥ 1 and suppose that r ζ p([2n + 1]) does not contain three distinct sets A, B, C such that A ∈ B ∈ C . Prove that IrI ≤ 2╱2n(n+1)、.(25 marks)

(a)  1, 12, 123, 1234, 12345 is a maximum sized intersecting chain (any larger chain must also contain 0 since it can contain at most one set of each size, but this would no longer be intersecting).  [4 marks]

(b)  The largest antichain has size at most  ╱2(5)、(by Sperner’s Theorem). The unique intersecting antichain of this size is ╱ [3(5)]、.  [4 marks]

(c) If A is an antichain in p([n]) then  AeA   ≤ 1.

[2 marks]

(d) We can adapt the proof of LYM to this case. Let r satisy the condi- tions given in the question and N = 2n+1. Construct a bipartite graph G with vertex classes r and SN  and an edge from F to π iff the first IF I elements of π are F . For each F we have dG (F) = IF I!(N 一 IF I)! (since the first IF I elements of any neighbour are F in some order and then we are free to choose the order of the elements in Fc . We claim no π  e SN   has degree greater than 2.   If not, say π is adjacent to distinct sets A, B, C e r then these sets are all intial elements from π, thus all have different sizes, wlog IAI < IBI < ICI and so we must have A ∈ B ∈ C, a contradiction. Hence dG (π) ≤ 2. Hence by double counting edges in G we have

1   ≤ 2.

F eF  ╱ ||、

Finally we note that since N = 2n + 1 then for any F e r we have ╱ |F(N)|、≤ ╱2n(n+1)、and the desired result follows.  [15 marks]

4.  For an integer n ≥ 3 and p e [0, 1] let F be a random graph from g(n, p).

(a)  Calculate the expected number of edges in F .

(b)  Calculate the expected number of triangles in F .

(c)  Calculate the expected number of vertices in F of degree 0.

(d)  Set p = 2/n and let t(F) be the expected number of pairs of distinct vertices x, y e V (F) such that the length of the shortest path from x to y is at least 3.

Explain carefully why t(F) is given by the following expression

(n 一 1)(n 一 2)n -1 (n + 2)n -2

2n2n -4                           . (25 marks)

(a)  Each  possible  edge  is  present  with  probability p  so  by  linearity  of expectation this is p ╱2(n)、.  [2 marks]

(b)  For each of of the  ╱3(n)、possible triangles T let XT  be the associated indicator variable. For a fixed triangle the probability it is present is p3 (since it contains three edges and these are each present independently with probability p).  So by linearity of expectation this is  ╱3(n)、p3 .   [3 marks]

(c)  For v  e  V (F),  d(v)  =  0 iff each of the  n 一 1 possible edges  vw , w  e V (F)/{v} is absent.   These are all absent independently with probability (1 一 p), so any single vertex has degree 0 with probability (1 一 p)n -1  and so the expected number of such vertices (by linearity of expectation) is n(1 一 p)n -1 .  [5 marks]

(d)  For a pair of vertices x, y the shortest path from x to y has length at least 3 iff xy is not an edge and not both of xi and yi are edges for any i  x, y . The probability that not both of xi and yi are edges for any fixed i  x, y is 1 一p2 and these edges are distinct for the n 一 2 different choices of i  x, y . Since these edges are distinct the associated events are independent and hence the probability that there is no i  x, y such that xi and yi are both edges is (1 一 p2 )n -2 .  Finally the probabilty that xy is not an edge is (1 一 p) and this edge is different from those considered previously so is absent independently of the other edges. Hence the probability that the shortest path from x to y has length at least 3 is (1 一 p)(1 一 p2 )n -2 .

Linearity of expectation then tells us that the expected number of such pairs is ╱2(n)、(1 一 p)(1 一 p2 )n -2 . Finally substituting p = 2/n we obtain the desired expression.  [15 marks]