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

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$.

Solved by gpt-5.6-sol high.