Four-Colour Conjecture true with additional hypothesis

123 Views Asked by At

Show that the Four-Color Conjecture is true provided that it is true for all simple $3$-connected maximal planar graphs.

I already know that a graph $G$ is planar if and only every $3$-connected component is planar. And that: Every $3$-connected planar graph has only one embedding.

I think it would be useful to reduce the graph to a triangulation and apply the extra hypothesis to the $3$-connected components, but I don't know exactly how to extend all the coloration of each $3$-connected component to the whole graph, so I would appreciate any hint!

Thank you!

1

There are 1 best solutions below

0
On

Each (simple) planar graph $G$ is a subgraph of a (planar) triangulation. Each triangulation (with at least four vertices) is 3-connected, so the hypothesis is applicable to it.