Q:

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

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.)

A:

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.

