prove that 3-colorability of planar graphs is NP-hard: (a) Prove that in any legal 3-coloring of the crossover gadget, the opposite corners are...

prove that 3-colorability of planar graphs is NP-hard:

(a) Prove that in any legal 3-coloring of the crossover gadget, the opposite corners are forced to have

the same color.

(b) Prove that any assignment of colors to the corners such that opposite corners have the same color

extends to a legal 3-coloring of the entire crossover gadget.

(c) Use the following idea to prove that 3-colorability of planar graphs is NP-hard: Replace each point

at which another edge crosses edge (u, v) with a copy of the crossover gadget G. For example, replace figure-1 with figure-2