Past exam of the mathematics course of the University of Cambridge 2020 ii Paper 2 17G ii Solution Created 2026-09-24 Updated 2026-09-29
For , choose a cycle for which some -bridge has at least three attachment vertices ; 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 , suppress degree-two vertices. The result has a branch vertex joined to by three paths whose interiors are mutually disjoint and avoid . The three arcs of between , together with these three paths, form a subdivision of the complete graph on branch vertices . Hence
A 3-connected graph need not contain a . The complete graph itself is 3-connected and has only four vertices, so it cannot contain a graph subdivision of . Equally, any planar 3-connected graph is a counterexample because a subdivision of the complete graph would be nonplanar.