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

A graph is eulerian graph if it has a closed trail containing every edge exactly once. For a graph with at least three vertices, the Euler circuit criterion says that it is Eulerian exactly when it is connected and every vertex has even degree.

Necessity is immediate: each visit of a closed trail to a vertex uses one entering and one leaving edge, so the incident edges occur in pairs; the trail also joins every vertex incident with an edge. Conversely, start at any vertex and extend an edge-simple trail until no unused incident edge remains. Even degrees force this maximal trail to end where it began. If edges remain, connectedness supplies a vertex of this circuit incident with an unused edge. Construct another closed trail from there and splice it into the first. Repeating consumes every edge and gives an Euler circuit.

The line graph $L(G)$ has vertex set $E(G)$, with two vertices adjacent when the corresponding edges of $G$ share an endpoint. If $G$ is connected and $r$-regular, then $L(G)$ is connected, and the vertex corresponding to an edge $uv$ has degreeEvery degree is even, so the Euler circuit criterion makes $L(G)$ Eulerian.

The Euler formula for a connected planar graph follows by induction on the number of cycle edges. If $G$ is a tree, then $e=n-1$ and $f=1$, so $n-e+f=2$. Otherwise remove an edge belonging to a cycle. The graph remains connected, while the two faces adjoining that edge merge: both $e$ and $f$ decrease by one. Thus $n-e+f$ is unchanged, and induction reaches a tree.

Every edge borders two face sides, so the sum of the face sizes is $2e$. If every face has size at least $g$, thenSubstitute $f=2-n+e$ from Euler's formula:and hence the planar girth edge bound

For each crossing pair, delete one of its two edges. At most $t(G)$ distinct edges are deleted, and the graph left behind has a crossing-free drawing. The planar graph edge bound therefore givessoThis is the linear estimate underlying the crossing lemma.

Choose each vertex independently with probabilityand take the induced drawing. Let its numbers of vertices, edges, and crossing pairs be $N,E,T$. Since crossing edges have four distinct endpoints,Part (i), with the harmless positive constant dropped, gives $T\ge E-3N$ for every outcome. Taking expectations,For $p=4n/e$, the right side is $4n^2/e$. Dividing by $p^4=256n^4/e^4$ proves the crossing lemma estimate