Connected four-valent link projections admit checkerboard colorings

Fix a point $x_0$ in a complementary region $R_0$. First decompose the edges of $P$ into finitely many edge-disjoint simple cycles. In a nonempty remaining even-degree graph, follow unused edges until a vertex first repeats; the segment between its two occurrences is a simple cycle, including a loop edge as a one-edge cycle. Removing that cycle subtracts two incident half-edges at each of its vertices and leaves every degree even. Repeat until no edge remains. This terminates because each removal deletes an edge; a vertex-free circle is already one cycle. Now choose two piecewise-smooth paths $\alpha ,\beta$ from $x_0$ to the same point in a region $R$, avoiding the finitely many vertices and meeting open edges transversely in finitely many points. Their concatenation $\gamma =\alpha \ast {\beta }^{-1}$ is a closed test path; it need not be embedded or be an edge-path of $P$. Its intersections are counted with traversal multiplicity, so $I(\gamma ,P)=I(\alpha ,P)+I(\beta ,P)$ modulo two. For each simple graph cycle, choose small vertex disks disjoint from the compact image of $\gamma$ and round that cycle inside them. The rounded cycle remains embedded and has exactly the same test-path intersections as its original edges. By [F2] it separates $S^2$ into two sides. Each transverse encounter switches the side occupied by $\gamma$, and a complete traversal returns to its initial side, even when the test path self-intersects or retraces an arc. Thus $\gamma$ meets each rounded cycle evenly. The graph cycles partition all open edges and $\gamma$ misses their vertices, so summing their intersection counts proves $I(\gamma ,P)=0$ modulo two. Therefore $\alpha$ and $\beta$ have the same crossing parity. Coloring $R$ by this parity gives a well-defined function, independent also of the chosen endpoint inside $R$, since two such endpoints are joined within $R$ without crossing $P$. All decompositions, rounding choices and perturbations are finite; no choice axiom is used.

Crossing one edge changes the parity by one, so adjacent regions receive different colors. The dual adjacency graph of regions is connected because a generic path between any two regions crosses finitely many edges; hence fixing the color of $R_0$ forces every other color. The two choices for the color of $R_0$ give exactly two colorings.