Canonical decompositions of 3-connected graphs

04/03/2023

∙

by   Johannes Carmesin, et al.

∙

0

∙

share

We offer a new structural basis for the theory of 3-connected graphs, providing a unique decomposition of every such graph into parts that are either quasi 4-connected, wheels, or thickened K_3,m's. Our construction is explicit, canonical, and has the following applications: we obtain a new theorem characterising all Cayley graphs as either essentially 4-connected, cycles, or complete graphs on at most four vertices, and we provide an automatic proof of Tutte's wheel theorem.