The Claim
Suppose $\gamma : [0,1] \to \mathbb{R}^2$ is a $C^1$ curve in the plane such that
- $\gamma(0) = \gamma(1)$
- $\gamma'(t) > 0$ for all $t \in [0,1]$
- $\gamma^{-1}(p)$ contains at most $2$ elements for all $p \in \mathbb{R}^2$.
Then $\gamma$ divides the plane into regions that can be colored with $2$ colors in such a way that adjacent regions do not have the same color.
Attempts at a Proof
This is presented as an elementary exercise in a textbook, but it's not obvious to me at all.
I tried to recast this as a graph theory problem, with the regions acting as vertices which are connected by an edge only if the regions are adjacent. After looking at a few examples, a proof didn't suggest itself to me.
I then tried to really use hypotheses 2 and 3 on $\gamma$. To me, what these hypotheses imply is that whenever $\gamma$ intersects itself, it does so by crossing itself. Moreover, when it crosses itself, it does so in such a way that the region it enters into is split into a well-defined left (in the direction of motion) part and right part. My idea was then to just color the left part one color and the right part the other color. However, this coloring doesn't actually work out. You'll sometimes color one region both colors according to this rule.
I tried variations on the previous idea but didn't get anywhere, at which point I decided to make this post.
I doubt that this is easy (it is not easier than the Jordan Curve Theorem). However, there is the following "standard" idea: pick a region in the complement of your curve, and draw a ray to infinity. This will intersect the curve in some number of points. The key observation is that the parity of the number of intersections only depends on the region and not on the point, nor on the direction of the line. If the line is tangent to the curve somewhere that counts as two intersections, and if the line goes through a double point, that also counts as two intersections. To make this into a complete argument, I strongly suggest reading:
Milnor, John W., Topology from the differentiable viewpoint, Charlottesville: The University Press of Virginia. IX, 64 p. (1965). ZBL0136.20402.