Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MATH0029 Graph Theory and Combinatorics

Section A

1. Let X = {1, 2, 3, 4, 5}. Carefully justifying your answers:

(a)  Give an example of a chain of maximum size in 伫(X).

(b)  Give an example of an antichain of maximum size in 伫(X).

(c) What is the maximum size of a family in 伫(X) that is both a chain and an antichain?

(d)  Give a partition of 伫(X) into symmetric chains.


2.   (a)  State Ramsey’s theorem.

(b)  Given that R(3, 4) = 9 prove directly (without using Ramsey’s theorem) that R(3, 5) ≤ 14.

(c) For t > 2 define R4 (t) to be the smallest integer n such that any edge colouring of Kn with 4 colours contains a monochromatic copy of Kt . Prove that for t > 6 we have R4 (t) > 2t .


3.   (a)  Give an example of a complete bipartite graph of order 6 containing a Hamilton cycle. Justify your answer.

(b)  Give an example of a complete bipartite graph of order 6 that does not contain a Hamilton cycle. Justify your answer.

(c) Let n > 2 and define Gn  to be the graph with vertex set {一1, +1}n  and edges given by

E(Gn ) = {uv | u, v ∈ {一1, +1}n  differ in exactly one coordinate}.

(i) For each n > 2 compute χ(Gn ). Justify your answer.

(ii) For which n > 2 does Gn  contain an Euler circuit? Justify your answer.   (iii) For which n > 2 does Gn  contains a Hamilton cycle? Justify your answer.


Section B

4.   (a) Let G be a graph of order n > 3.  Prove that either G is complete r-partite, for  some  r  >  1,  or  G  contains  an  induced  subgraph  isomorphic to  H  = ({a, b, c}, {ab}).

(b)  Call a graph G maximal F -free if G is F-free but the addition of any new edge to G creates a copy of F .

(i) Prove that if G is maximal K3-free then either G is complete bipartite or G contains a copy of C5 .

(ii) Prove that if G is maximal K4-free then either G is complete 3-partite or G contains a copy of either H1  or H2  (see below)

H1  = ({a, s, t, u, v, y, z}, {as, at, au, av, st, uv, yz, sy, ty, uz, vz})

H2  = ({a, s, t, u, y, z}, {as, at, au, st, tu, yz, sy, ty, tz, uz}).

Figure 1: The graphs H1  and H2


5.   (a) How many edges does the Tur´an graph T4 (9) contain?

(b) For which values of n > r > 2 does T4 (9) contain a copy of Tr (n)? Justify your answer.

(c)  Calculate, with justification, the Tur´an density of each of the following graphs: K3 , K3,3 , T4 (2020).

(d) Let H be a graph with at least one edge and Tur´an density π(H) = α.  Let H*  be formed from H by adding two new vertices a, b and adding new edges {ab} U {va, vb | v ∈ V (H)}.  What is the Tur´an density of H* ?  Justify your answer.