# 2 color theorem

Remember 4 color theorem: any map in a plane can be colored with 4 colors so that no two adjacent regions have the same color.

Draw a map: Put your pen to paper, start from a point P and draw a continuous line and return to P again. Do not redraw any part of the line but intersection is allowed.

All maps I drew in this way can be colored with 2 colors so that no two adjacent regions have the same color.

can you find a counterexample or do you know any theorems in graph theory about such maps?

(all I know about graph theory is what I remember from highschool.)

Edit:

Let M be a map which can be colored with 2 colors so that no two adjacent regions have the same color. Can M be drawn as described above?

-
You mean I pick an arbitrary graph, start from an arbitrary point, draw a line an come back, and look at the new graph? –  Anon Feb 1 '13 at 1:53
Oh I got it now, you start from a blank paper but your line can self-intersect :) –  Anon Feb 1 '13 at 1:54
yes____________ –  user59671 Feb 1 '13 at 1:55
The 4 color theorem states that any map on the plane can be 4-colored. It might take more than 4 colors to color a map on, say, the surface of a bagel (where you need 7 for some maps). –  Rick Decker Feb 1 '13 at 2:10
fixed---------------- –  user59671 Feb 1 '13 at 2:13

I assume that during the drawing process you do not allow retracing of part of a line that's already been drawn. If you do then there is a counterexample.

If you don't allow that then observe that every vertex of the graph has even degree because as you drew you had to pass in to that vertex exactly as many times as you passed out.

Using that fact one can show that the result can in fact be 2-colored.

-
Couldn't have said it better myself. –  Joe Z. Feb 1 '13 at 1:59
yes do not redraw part of a line. I'll fix my post. –  user59671 Feb 1 '13 at 2:00
Maybe I'm missing something obvious, but this answer seems a little too terse. The cycle on $3$ vertices has all even-degree vertices, but is not $2$-colourable. –  Rahul Feb 1 '13 at 2:08
@$\Bbb{R^n}$: But its dual graph is! –  Micah Feb 1 '13 at 2:13
@$\mathbb R^n$: "Vertices" here means any self crossing in the line drawn by the OP. –  Jim Feb 1 '13 at 2:13

Re the edit: No. For example, a map consisting of several concentric circles is $2$-colorable, but can't be drawn as you're describing.

However, if you add in the condition that your boundaries all connect to each other, the answer becomes "yes", by Euler's famous Königsberg bridge solution.

-

The 2-colorable graphs are bipartite graphs: a graph is bipartite iff it is 2-colorable.

-