1.II.17H

Graph Theory | Part II, 2007

Let GG be a connected cubic graph drawn in the plane with each edge in the boundary of two distinct faces. Show that the associated map is 4 -colourable if and only if GG is 3 -edge colourable.

Is the above statement true if the plane is replaced by the torus and all faces are required to be simply connected? Give a proof or a counterexample.

Typos? Please submit corrections to this page on GitHub.