# Reducing 3-colouring to planar 3-colouring

I was reading these lecture notes and I'm trying to understand how one would formally describe reducing 3-colouring to planar 3-colouring. The link pretty much describes the process but understanding the mathematical formalism is a bit over my head. In short, it seems that every edge crossing is replaced with some new graph. How does this work?

-

The idea is to replace each crossing with a certain planar gadget $W$, which functions as a cloverleaf. The four vertices on the outside of the gadget consist of a horizontal pair $x_1,x_2$ and a vertical pair $v_1,v_2$. The gadget has the property that in any valid 3-coloring $c$, $c(x_1) = c(x_2)$ and $c(v_1) = c(v_2)$, and vice versa, for each choice of $c(x_1) = c(x_2)$ and $c(v_1) = c(v_2)$ there is such a coloring.
How do we use this gadget? Suppose that the graph has exactly one crossing, the edge $(a,b)$ crossing the edge $(r,s)$, we put a copy of the gadget with $x_1 = a$ and $v_1 = r$. The gadget ensures that $c(x_2) = c(a)$ and $c(v_2) = c(r)$, so if we connect $x_2$ to $b$ and $v_2$ to $s$, the new graph is 3-colorable iff the original one is (I encourage you to draw this, consulting the lecture notes). Plus, the crossing has been replaced by the gadget, which is itself planar.