Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 2 / 17G (Graph Theory)

For nonadjacent vertices $a,b$, the local connectivity $\kappa (a,b;G)$ is the minimum cardinality of an $a$-$b$ vertex separator: a set $S\subseteq V(G)\setminus \{a,b\}$ such that $a$ and $b$ lie in different components of $G-S$.

To prove the vertex form of the Menger theorem, replace every vertex $v\notin \{a,b\}$ by an arc $v_{\mathrm{in}}\to v_{\mathrm{out}}$ of capacity one. Replace every undirected edge $uv$ by directed arcs from $u_{\mathrm{out}}$ to $v_{\mathrm{in}}$ and conversely, each of capacity larger than $|V(G)|$; leave $a,b$ unsplit. An integral $a$-$b$ flow of value $k$ decomposes into $k$ paths, and the unit-capacity vertex arcs force the corresponding graph paths to be internally vertex-disjoint paths. Conversely, $k$ such paths give an integral flow of value $k$.

Because $a$ and $b$ are nonadjacent, any finite minimum cut consists entirely of unit-capacity vertex arcs. These arcs correspond exactly to an $a$-$b$ vertex separator of the same size. The max-flow min-cut theorem, whose augmenting-path proof also guarantees an integral maximum flow for integral capacities, therefore givesIn particular, $G$ contains the required set of $\kappa (a,b;G)$ paths.

A 3-connected graph contains a cycle, and any cycle is a complete graph subdivision $T{K}_3$.

For $T{K}_4$, choose a cycle $C$ for which some $C$-bridge has at least three attachment vertices $a,b,c$; such a choice is always possible in a 3-connected graph. Indeed, every component outside a cycle has at least three attachments, since one or two would form a vertex cut, and if a chosen cycle is spanning, a chord can be used to choose a smaller cycle and expose the remaining bridge. In a minimal connected part of that bridge joining $a,b,c$, suppress degree-two vertices. The result has a branch vertex $w$ joined to $a,b,c$ by three paths whose interiors are mutually disjoint and avoid $C$. The three arcs of $C$ between $a,b,c$, together with these three paths, form a subdivision of the complete graph on branch vertices $w,a,b,c$. Hence

A 3-connected graph need not contain a $T{K}_5$. The complete graph $K_4$ itself is 3-connected and has only four vertices, so it cannot contain a graph subdivision of $K_5$. Equally, any planar 3-connected graph is a counterexample because a subdivision of the complete graph $K_5$ would be nonplanar.