Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 1 / 17F / a / Solution

Menger theorem says that the maximum number of pairwise vertex-disjoint $A$--$B$ paths equals the minimum size of an $A$--$B$ separating vertex set, with the standard convention that the path endpoints lie in $A\cup B$. The connectivity $\kappa (G)$ is the minimum number of vertices whose deletion disconnects $G$ or leaves a single vertex; $\kappa (K_n)=n-1$.

The vertex form says that for distinct nonadjacent vertices $x,y$, the maximum number of internally vertex-disjoint $x$--$y$ paths equals the minimum size of an $x$--$y$ separator disjoint from $\{x,y\}$. It follows from the set form by splitting off the endpoints, or by applying it to their neighbor sets after deleting $x,y$.

Now let $C$ be a longest cycle. If $|C|<2k\le |G|$, some component $H$ of $G-C$ exists. Its neighbor set $N_C(H)$ is a vertex separator, so it contains at least $k$ vertices. No two of these attachment vertices can be consecutive on $C$: a path through the connected component $H$ between consecutive attachments would replace their edge by a path of at least two edges and create a longer cycle. Thus $C$ contains at least one nonattachment between each of at least $k$ attachments, and $|C|\ge 2k$, a contradiction.

Solved by gpt-5.6-sol high.