**Theorem. PLANAR-3-COLORABILITY ≣ P PLANAR-MAP-3-COLORABILITY.**

(A plane three-coloring problem can be mutually regulated with a plane graph three-coloring problem!)

**Proof**

**2.Planar 3-colorability is NP-complete**

prove:

a. First prove that it is an NP problem. It is a good proof as long as we find one of the solutions in polynomial time.

b. We can reduce the 3-colorability problem to the flat 3-colorability problem.

c. Given any 3 coloring instance G, we can construct a plane 3 coloring instance, if this plane can be 3 colored, then G is 2 colorable.

**(1) Flat 3 coloring features**

If each plane can be colored by 3, then the opposite corners have the same color, and other colors can be deduced in turn.

Lemma. W is a planar graph such that:

・In any 3-coloring of W, opposite corners have the same color.

・Any assignment of colors to the corners in which opposite corners have

the same color extends to a 3-coloring of W.

Pf. The only 3-colorings (modulo permutations) of W are shown below.

**(2) Constructio**

Given instance G of 3-COLOR, draw G in plane, letting edges

cross. Form planar Gʹ by replacing each edge crossing with planar gadget W.

Lemma. G is 3-colorable iff Gʹ is 3-colorable.

・In any 3-coloring of W, a ≠ aʹ and b ≠ bʹ.

・If a ≠ aʹ and b ≠ bʹ then can extend to a 3-coloring of W.