Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 2 / 17G (Graph Theory)

Choose a vertex $v$ of $K_6$. At least three of its five incident edges have one colour, say blue, by the pigeonhole principle. Let their other endpoints be $x,y,z$. If one of $xy,yz,zx$ is blue, it completes a blue triangle with $v$; if none is blue, $xyz$ is a yellow triangle. Thus every colouring of $K_6$ has a monochromatic triangle.

The statement fails for $K_5$. Colour the edges of a five-cycle blue and its complementary five-cycle yellow. Neither colour contains a triangle.

Use the two-colour matching Ramsey numberIts upper bound follows by induction on $s$. If there is a blue edge, remove its endpoints and apply the induction hypothesis to the remaining $K_{2r+s-3}$: it contains either a red $r$-edge matching or a blue $(s-1)$-edge matching, and in the latter case the removed edge completes a blue $s$-edge matching. If there is no blue edge, the graph itself contains a red $r$-edge matching. For $r=s=t$, this gives the required monochromatic matching in $K_{3t-1}$.

The result never remains true for $K_{3t-2}$, including $t=1$. Partition its vertices into $A$ and $B$ with $|A|=2t-1$ and $|B|=t-1$. Colour edges within $A$ blue and every other edge yellow. A blue matching has at most $t-1$ edges, while every yellow edge meets $B$, so a yellow matching also has at most $t-1$ edges.

Let $B=\{b_1,b_2,b_3\}$ be a blue triangle and $Y=\{y_1,y_2,y_3\}$ a vertex-disjoint yellow triangle. If some $b_i$ has two yellow neighbours in $Y$, those three vertices form a yellow triangle meeting $B$. Otherwise every $b_i$ has at least two blue neighbours in $Y$, giving at least six blue cross-edges. Some $y_j$ then has two blue neighbours in $B$, and these form a blue triangle meeting $Y$. This proves the overlap assertion.

The triangle-packing Ramsey number isFor completeness, its induction starts from the stated $K_{10}$ result. At each step, remove two disjoint monochromatic triangles supplied on ten currently unused vertices. If their colour disagrees with the packing already constructed, apply the overlap assertion to an oppositely coloured pair; replacing that pair by the overlapping pair is the augmenting move that shifts the boundary between the two packings. Repeating the move either adds a triangle to the existing colour or converts all pairs needed for the opposite-colour packing. Thus $K_{5t}$ contains $t$ pairwise vertex-disjoint monochromatic triangles of one colour.

The bound is sharp. For $K_{5t-1}$, split the vertices into $A,B_1,B_2$ withColour edges inside $A$ and between $B_1$ and $B_2$ yellow; colour all edges from $A$ to $B_1\cup B_2$ and all edges within each $B_i$ blue. Every yellow triangle lies wholly in $A$, so there are at most $t-1$ disjoint yellow triangles. Every blue triangle uses at least two vertices of $B_1\cup B_2$, and $t$ such triangles would require a blue perfect matching on those $2t$ vertices, impossible because the isolated one-vertex blue component $B_1$ and the odd component $B_2$ have no such matching. Hence there is no $t$-triangle packing of either colour for any $t\ge 2$.