= 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\leq|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|\geq2k$, a contradiction.
Back to article page
