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

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.

The edge connectivity $\lambda (G)$ is the minimum number of edges whose deletion disconnects $G$. Deleting all edges incident with a minimum-degree vertex proves $\lambda (G)\le \delta (G)$. For a minimum edge cut separating vertex sets $A,B$, its endpoints on either suitable side give a vertex separator of size at most the number of cut edges; the complete-graph convention gives the same conclusion. Hence

To realize prescribed $d\ge \ell \ge k\ge 1$, take two disjoint copies $A,B$ of $K_{d+1}$. Add a bipartite set of exactly $\ell$ cross edges whose maximum matching has size $k$: include $a_i{b}_i$ for $1\le i\le k$, and, when $\ell >k$, add $a_1{b}_j$ for $k<j\le \ell$. This is simple because $\ell \le d$, has a matching of size $k$, and all its edges are covered by $\{a_1,\dots ,a_k\}$.

Vertices untouched by cross edges have degree $d$, so $\delta (G)=d$. The cross edges form an edge cut of size $\ell$; every cut that splits either clique uses at least $d\ge \ell$ clique edges, hence $\lambda (G)=\ell$. By König's theorem, the cross graph has a vertex cover of size $k$, whose deletion separates the two surviving clique pieces. Deleting fewer than $k$ vertices leaves each clique connected and at least one cross edge, so $\kappa (G)=k$.