Graph decompositions and a counterexample to a meta-conjecture

Carsten Thomassen gave an interesting invited lecture at Graph Drawing, on graph decompositions: partitions of the edges of graphs into subgraphs of a fixed type. For instance, a Schnyder labeling of a maximal planar graph, important in graph drawing for its applications in embedding planar graphs into grids, can be interpreted as a partition of the graph into one triangle (the outer face) and \( n-3 \) claws (the three outward edges from each vertex). A Steiner triple system is just a decomposition of the complete graph into triangles; such a decomposition exists whenever the graph satisfies the obvious necessary conditions that the vertices have even degree and the number of edges be divisible by three. Every graph with an even number of edges can be decomposed into length-two paths: equivalently, every line graph and more generally every claw-free graph has a perfect matching.

A decomposition into claws is essentially the same thing as an orientation of the edges of the graph so that every vertex has an outdegree that's divisible by three: in one direction, just orient each claw outwards from its center, and in the other direction, partition the outgoing edges at each vertex into claws. With Barat, Thomassen proved that \( K_4 \) is the only graph of a triangulated surface that does not have a decomposition into claws. He also showed that there is a constant \( k \) such that every \( k \)-edge-connected graph (satisfying the obvious necessary condition that the number of edges be divisible by three) has a decomposition into claws. More strongly, if Tutte's conjecture that every 4-edge-connected graph has a nowhere zero 3-flow (equivalently an orientation such that indegree and outdegree are congruent mod 3 at every vertex) is true, then \( k = 10 \) would suffice. But the following graph shows that \( k = 4 \) is not good enough: each of the three \( K_4 \) subgraphs (the three crossed circles in the drawing) can only be covered by having three claw centers within the \( K_4 \), but the resulting nine centers would be too many for the total number of edges in the graph.

Thomassen made a meta-conjecture, that Tutte has never made a wrong conjecture. But unfortunately there's a counterexample. In a 1971 paper ("On the 2-factors of bicubic graphs", Discrete Mathematics 1: 203–208) Tutte conjectured that every 3-connected bipartite cubic graph is Hamiltonian and more strongly that the Hamiltonian cycles form a cycle basis. But it's not true: the Horton graph is 3-connected, bipartite, cubic, and non-Hamiltonian.

Comments: