A Tutte-type canonical decomposition of 3- and 4-connected graphs

We provide a unique decomposition of every 4-connected graph into parts that are either quasi-5-connected, cycles of triangle-torsos and 3-connected torsos on ⩽ 5 vertices, generalised doublewheels, or thickened K4,m's. The decomposition can be described in terms of a tree-decomposition but with edges allowed in the adhesion-sets. Our construction is explicit, canonical, and exhibits a defining property of the Tutte-decomposition.

As a corollary, we obtain a new Tutte-type canonical decomposition of 3-connected graphs into parts that are either quasi-4-connected, generalised wheels or thickened K3,m's. This decomposition is similar yet different from the tri-separation decomposition [CK23].

As an application of the decomposition for 4-connectivity, we obtain a new theorem [KP26] characterising all vertex-transitive finite connected graphs as essentially quasi-5-connected or on a short explicit list of graphs.