2 color theorem

Question

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?
Oh I got it now, you start from a blank paper but your line can self-intersect :)
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).

Jim · Accepted Answer · 2013-02-01 01:57:39Z

up vote 5 down vote accepted

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.

answered Feb 1 at 1:57

Jim
8,3872735

Couldn't have said it better myself. – Joe Z. Feb 1 at 1:59

yes do not redraw part of a line. I'll fix my post. – user59671 Feb 1 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 Narain Feb 1 at 2:08

1

@$\Bbb{R^n}$: But its dual graph is! – Micah Feb 1 at 2:13

@$\mathbb R^n$: "Vertices" here means any self crossing in the line drawn by the OP. – Jim Feb 1 at 2:13

Micah · Answer 2 · 2013-02-01 02:48:21Z

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.

ashley · Answer 3 · 2013-02-01 02:02:05Z

up vote 1 down vote

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

answered Feb 1 at 2:02

ashley
5218

asked	3 months ago
viewed	172 times
active	3 months ago

2 color theorem

3 Answers

Your Answer

2 color theorem

3 Answers

Your Answer

Sign up or log in

Post as a guest

Related