Vrftsjtryk

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?

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.

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.

(I know this thread is years old, but I thought maybe somebody might still be interested in that proof you were asking for.)

I think if you relax the requirement of drawing a single closed geometrical shape in the way you describe (without lifting the pen and without drawing on top of existing line segments), but also allow multiple such shapes (no matter if it crosses itself and/or any of the perhaps already existing lines), then I think indeed any 2-colorable graph can be drawn like this.

But first I start with the (perhaps more interesting?) "=>"-direction: "If a graph is drawn in the way as described above, it is always 2-colorable."

People have already realised, that the Graph G, where the line intersections are the vertices, and line segments connecting two vertices are edges, is an Euler graph, because obviously, all vertices have even degree (intersecting a line creates a new vertex with degree 4, crossing an already existing vertex adds 2 to its degree), and we can assume (without losing generality), that the graph is connected (if it's not, the following proof applies to each connected sub-graph analogously).

Also, it is obvious to see, that a bipartite graph is always 2-colorable (first partition of vertices: color 1, second partition: color 2). So what's left to be shown is, that if a planar graph G is Eulerian, then its dual graph G' is always bipartite (and therefore 2-colorable, obviously).

[I hereby show a contradiction proof, which uses the property, that the dual of a dual Graph should be isomorphic to the original Graph, so G'' = G. The proof idea was taken from Jorge Fernandez: Prove that the graph dual to Eulerian planar graph is bipartite. ]

Let's assume G is Eulerian, but G' is NOT bipartite. Since it is not bipartite, it contains at least one odd cycle (cycle with an odd number of vertices). The proof for this is rather straight-forward (and can be found on youtube...). If we could show, that this Graph G' contains at least one face with an odd number of adjacent edges, this means that G'' is NOT Eulerian, because the respective vertex in G'' representing that face in G' will have odd degree! -- On the other side, it MUST be Eulerian, because it is isomorphic to G, which is Eulerian as to our assumption. => contradiction of the assumption.

So what remains to be shown is, that a graph containing at least one odd cycle always contains such a face with an odd number of adjacent edges. Let's have a look at one of the odd cycles in G' (it contains at least one such cycle, so let's just pick any). Since G' is planar (because G is), I think it is valid here to talk about things being "outside" or "inside" the cycle. We are only looking here at things inside that odd cycle "C". So let's look at our odd cycle C, and distinguish between the following two cases:

(1) Inside of C, there are no edges or vertices. That means we have found a face with an odd number of adjacent edges (the cycle surrounds that face) --> FINISHED.

(2) Inside of C, there is some cycle-free path P=[i,a1,a2,...,j], connecting two vertices i and j of the cycle. [It could as well just be P=[i,j], so a direct edge from i to j, splitting our cycle in two parts.] So let's split C along that path P, yielding two cycles C1 and C2. What is the total number of vertices |C1|+|C2| now? Well, i and j have to be counted twice now, as they are contained in both new cycles, and the same holds for the intermediate vertices (if any) a1,a2,... So: |C1|+|C2|=|C|+2*|P|. Apparently, this sum does not change the parity: If |C| was odd, then also |C1|+|C2| is odd, and therefore either |C1| or |C2| must be odd. We now choose the odd cycle, and start over with this cycle.

We can be sure, that this process terminates after a finite number of steps (if the number of edges is finite), finally "finding" an odd-edged face, because the number of edges enclosed in C will reduce in each step. Further, from the statements above it is clear that there is always an odd-cycle (we can never end up with two even cycles after the splitting step).

Discussion: I think from the way how we created G', there are no more special cases to examine. For example, isolated vertices, or vertices inside C which are connected to C only via a single connection, are impossible from the way how G' was constructed: This would mean, that G' is not a map, and so G'' would not be defined, I guess (but it must be, because G=G''). [Does anybody have a counter-example? Are there any special cases that I forgot?] There are examples without cycles in G' at all, but then of course we are looking at a tree, which is obviously bipartite, which is against our assumption.)

The reverse direction "<=": "A two-colorable graph can always be drawn as indicated above (allowing multiple closed planar shapes)." [Micah commented on this already, I just repeat his solution with my own words]

The dual graph G' of a two-colorable graph G is always bipartite. [Again: this is just obvious.] A bipartite graph is known to contain only even cycles. This is already known to be equivalent to the Euler property if we assume, that the graph is connected. If the graph is not connected (but consists of multiple connected components G1', G2', ...), the above statement holds for each components individually, meaning that each conponent fulfills the Euler property -- and thus, each component can be drawn without lifting the pen, and without drawing on top of an already existing line.