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

Repeatedly delete a vertex whose current degree is less than $d/2$. If every vertex were deleted, charge each edge to the endpoint deleted first. At each deletion fewer than $d/2$ remaining edges are charged, so the original graph would have fewer than $|V|d/2$ edges, contradicting average degree at least $d$. The nonempty graph left by the process has minimum degree at least $d/2$.

Set $N=(100\delta {)}^g$ and take $G\sim G(N,4\delta /N)$. Its expected number of edges is asymptotic to $2\delta N$, and a Chernoff bound makes $e(G)>3\delta N/2$ with positive probability. The expected number of cycles of length below $g$ is at mostwhich is far below $\delta N/2$; Markov's inequality shows that, simultaneously with positive probability, there are fewer than $\delta N/2$ such cycles.

Choose such a graph and delete one edge from every cycle of length below $g$. The resulting graph has girth at least $g$ and more than $\delta N$ edges, hence average degree greater than $2\delta$. Part (a) supplies a subgraph of minimum degree at least $\delta$. It uses at most $N=(100\delta {)}^g$ vertices and cannot acquire any shorter cycle.