Given two distinct colors, show that every adjacent region is different

Question

This question is difficult to quantify; it came up while I was working on an art project.

The basic idea is this: Suppose we have two colors "red and "blue," and a set of loops and start by assigning an arbitrary region "0" a color red. Then for every consecutive, adjacent region, we follow this rule:

• If an adjacent region was red, assign blue;
• If an adjacent region was blue, assign red;
• Repeat the rule for regions left out.

If we complete the rule, does it follow that no adjacent regions share the same color? A similar question: does our choice of adjacent regions affect the outcome?

Another way to think about this is to distinguish between even and odd regions.

I attached drawings to clarify what I meant by a loop. One way I might define it is that a loop's endpoints must meet. Intersections are legal, but an overlap over some interval is illegal. Finally, a loop may be as complicated as you want.

(What's better way to ask this question? I'm curious to know what specialization this would be a problem of.)

Answer 1

This is a problem that can be tackled with Graph Theory. We can place a vertex in each region of your drawing, then connect two vertices with an edge if the corresponding regions share a side. The problem is then equivalent to asking if the graph is $2$-colorable, or bipartite.

Indeed, any graph obtained this way will be bipartite. For each region, we can count the number of “loops” it is contained in. Before doing so, we will slightly adjust our set of loops. If a loop crosses itself, we will break it into two loops at the crossing point. In this way, we can assume that none of our loops cross themselves, and so there is a well defined “inside” and “outside” for each loop.

Now, note that a region that is contained in an even number of loops will only be adjacent to regions in an odd number of loops (because passing through the side between these regions will change the total number of loos you are in by 1.), and similarly regions in an odd number of loops will only be adjacent to regions in an even number of loops. Thus the graph is bipartite, so the regions can be $2$-colored.

Now that we know this can be $2$-colored, your algorithm will surely work to find a coloring as long as you color regions adjacent to previously colored regions.

Answer 2

The Jordan Curve Theorem says that any loop in the plane separates the plane into two regions: the interior, which is bounded, and the exterior, which contains all points sufficiently far for from the origin. This theorem allows to prove your conjecture by induction:

If there is no loop given paint all points blue.

Assume that $n$ loops $\ell_k$ $(0\leq k\leq n)$ have already been drawn. By induction hypothesis these loops partition the plane into subregions that can be colored as you describe, with the single unbounded region blue. Now add a next loop $\ell_{n+1}$ that does intersect all existing loops transversally, and does not pass through an existing point of intersection. This loop will have an interior that contains some existing and colored regions in part, and others in total. Change the color of all such (sub)regions in the interior of $\ell_{n+1}$. In this way you obtain an admissible coloring of the new configuration.