Bulletin of the Australian Mathematical Society

Research Article

Polyhedral decompositions of cubic graphs

G. Szekeresa1

a1 School of Mathematics, University of New South Wales, Kensington, New South Wales.

Abstract

A polyhedral decomposition of a finite trivalent graph G is defined as a set of circuits S0004972700042660_inline1 = {C1, C2, … Cm} with the property that every edge of G occurs exactly twice as an edge of some Ck. The decomposition is called even if every Ck is a simple circuit of even length. If G has a Tait colouring by three colours a, b, c then the (a, b), (b, c) and (c, a) circuits obviously form an even polyhedral decomposition. It is shown that the converse is also true: if G has an even polyhedral decomposition then it also has a Tait colouring. This permits an equivalent formulation of the four colour conjecture (and a much stronger conjecture of Branko Grünbaum) in terms of polyhedral decompositions alone.

(Received January 05 1973)