Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 3 / 17H (Graph Theory)

We prove the Quadratic Turan edge bound by induction. The case $r=1$ is immediate. For $r\ge 2$, if $G$ contains no $K_r$, the induction hypothesis for $r-1$ gives the stronger bound. Otherwise choose a copy $S$ of $K_r$. Every vertex outside $S$ has at most $r-1$ neighbours in $S$, since one adjacent to all of $S$ would complete a $K_{r+1}$. Thus the number of edges having at least one endpoint in $S$ is at mostThe graph $G-S$ is still $K_{r+1}$-free, so induction on the number of vertices givesThis proves the stated form of Turan theorem.

Letbe a longest path in $G$. Every neighbour of either endpoint lies on $P$. Suppose $\ell <2\delta (G)$. Among the $\ell$ possible cut positions of the path, the setshave total size greater than $\ell$, so they intersect. The corresponding two edges close a cycle containing all vertices of $P$.

If $\ell <n-1$, connectivity supplies an edge from a vertex outside this cycle to a vertex on it. Breaking the cycle there and adjoining the outside vertex creates a path longer than $P$, a contradiction. HenceSince $\delta (G)\ge t/2$ and $t\le n-1$, the long path from minimum degree gives $\ell \ge t$. Thus $G$ contains $P_t$.

Colour the vertices of $K_{(s-1)t}$ in $s-1$ groups of size $t$. Colour edges within groups blue and edges between groups red. The red graph is complete $(s-1)$-partite, so it has no red $K_s$. Every blue component has only $t$ vertices, so it has no path of length $t$. Therefore

We first derive the Erdos-Gallai path edge bound from part b. If an $n$-vertex graph has no path of length $t$, thenInduct on $n$, component by component. A component with at most $t$ vertices satisfies the bound trivially. A larger connected component cannot have minimum degree at least $t/2$ by part b, so delete a vertex of degree less than $t/2$ and apply induction; the integer degree removed is at most $(t-1)/2$, which preserves the bound.

Now setand consider a red-blue colouring of $K_n$. If there is no red $K_s$, part a with $r=s-1$ givesConsequentlyThe path edge bound forces a blue $P_t$. Together with part c this proves the clique-path Ramsey number