Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am self-studying Discrete Mathematics, and there is the following exercise. (in Portuguese)

A plane is divided by many lines. Show that it is possible to color the regions formed with only two colors so that no two adjacent regions share the same color.

First of all, I was not able to solve it. Then I did I search on Google, and I've find the following here.

4.Show that if n lines are drawn on the plane so that none of them are parallel, and so that no three lines intersect at a point, then the plane is divided by those lines into $\dfrac{n^{2} + n + 2}{2}$ regions.

The next exercise is:

  1. Show that if the same lines as in problem $4$ are drawn on a plane that it is possible to color the regions formed with only two colors so that no two adjacent regions share the same color.

Proof: With zero lines, you can obviously do it; in fact, one color would be sufficient. If you can successfully $2$-color the plane with $k$ lines, when you add the $(k + 1)$st line, swap the colors of all the regions on one side of the line. This will provide a $2$-coloring of the configuration with $k + 1$ lines. (In fact, for this problem, there is no real need to have the lines in general position: some can be parallel, and multiple lines can pass through a point, and the proof will continue to work.)

I did a drawn, and I got convinced, but I did not understand it. I am feeling stupid, but I was not able to understand the proof without drawing.

I would appreciate your help.

share|improve this question

5 Answers 5

up vote 5 down vote accepted

I will try to explain the proof you have found instead of giving another one.

The proof is, in fact, by induction. You start with one line and two regions: one black and one white. We want to show that if we have already drawn $k$ lines and painted all regions such that no two adjacent regions share the same color, then we can add any new $(k+1)$th line and repaint some regions (newly created and old ones) such that the property holds: no two adjacent regions share the same color.

Draw a new line, and do NOT change any colors for now. Consider both sides of the new line. No two regions on the same side of the new line are painted same color! This is because you did not change any colors, and any two regions on the same side may share only a part of a line which they shared before you drew a new line. Moreover, if you invert the colors of all regions on same side of the new line, then this property will still hold for them (blacks become white, and whites become black).

When you draw a new line, you create new regions by dividing some regions in two parts. These and only these newly created adjacent regions will share same color. But once you invert the colors of all regions on one side, you get what you need. All adjacent regions on either side are still painted in different colors, and now newly created adjacent regions (which share the same side which is a part of the new line) are opposite colors as well, because one of them got inverted.

share|improve this answer

For every line drawn, choose a nonzero affine (linear plus a constant) function with values in $\mathbf R$ that vanishes on the line. Then colour points $P$ not on any of the lines according to the sign of the product of all these functions at $P$.

Similarly you can replace the straight lines by any curves that can be defined as the zeros of a continuous function and get a more general result.

share|improve this answer

Say you already have a plane with N lines on it which is 2-colorable. Then draw another line. Even though this line may cut through regions of various colors, for any point on this line, the newly created regions on both sides will always be the same color.

Then, in order to make this new map 2-colorable, pick one side of the new line and reverse all of the colors in that half of the plane. If the two colors were green and red, all of the red will become green and all of the green will become blue. For all old boundary points (a point an a boundary line) on either half of the plane, both sides (which were 2 different colors at the beginning) will still be two different colors, just flipped.

On the newly created line, since only one side of the line was flipped, and all parts of the line originally had the same color on both sides, all parts of the line now have different color on each side.

So, the plane with the added line is still 2-colorable. This means that if any plane with N lines is 2-colorable, then so is a plane with N+1 lines. Now, observe that an empty plane is 2-colorable (even though it only needs 1 of the 2 colors). So, a plane with any number of lines on it is 2-colorable.

share|improve this answer

You have a finite number of lines. Maybe some of them are parallel, maybe they all intersect each other. Either way, you get a finite set of intersection points. Draw a large circle that contains all the intersection points. Outside the circle, pick a point $P_0$ that does not lie on any of the lines. Color the region containing $P_0$ with color A. Now, draw a curve leaving $P_0$ that visits every region but never passes through an intersection, and for that matter always crosses every line it meets at a nonzero angle (no tangency). Every time your curve meets a region, give the region a color. If the curve has crossed lines an even number of times, color that region A, same as the region with $P_0.$ If the curve has crossed lines an odd number of times, color that region B. Keep extending the curve, crossing itself as needed, until every region has a color.

Why, if the curve visits a region more than once (very likely to happen), does the color assignment stay the same? Every region is on one or the other side of every line, even when the line does not meet the boundary of the region. To start at a region and get back to the same region, you must cross each line an even number of times, possibly $0.$ So every time you return to the same region, you get the same answer as far as odd/even number of crossings since beginning at $P_0.$ Plus, as required, to get from one region to another region which shares a line segment as boundary, you make exactly one crossing, therefore switching color.

EDITTTTT: Note that this proof works for planes in $\mathbb R^3.$

share|improve this answer

For convenience, do this on the sphere. Then your great circles determine a 4-regular embedded graph. Now make the Poincare dual graph which has a vertex for each region and an edge when two regions share an edge of the original graph. The dual has a cycle basis made of 4-cycles, and therefore doesnt have odd cycles. In other words, it is bipartite. This is, I guess, the argument from the planar graph perspective.

Update: Mariano points out that I am assuming that my great circles are such that all the intersections are simple. If not, then we can get vertices of degree more than 4 in the primal and vertices of degree 2 in the dual. The vertex degrees of the primal are still even, though, so the same argument applies to exclude odd cycles in the dual.

Another cool proof, that is due (I am told) to Lou Kaufman is this: "resolve" the intersections by replacing an X with a $\cup$ above a $\cap$. If you do this to all the intersections, you get a bunch of nested circles, which obviously have the property you want. Now undo the process.

share|improve this answer
    
If you have exactly three incident lines, the dual graph is an hexagon, and none of its cycle bases is made of 4-cycles! –  Mariano Suárez-Alvarez Mar 20 '12 at 21:47
1  
Also, your obviously at the end is more or less the Jordan curve theorem :) –  Mariano Suárez-Alvarez Mar 20 '12 at 21:59
    
Yes, both of these proofs require general position for the great circles. –  Louis Mar 20 '12 at 22:10
    
It's also quite a bit easier to argue the Jordan curve theorem for circles, or, as the question implicitly is doing, lines, for that matter. Marc is basically doing that. ;) –  Louis Mar 20 '12 at 22:14
    
Louis, in the general case, the space of cycles of the dual graph is spanned by the cycles one finds around each of the intersection points of the configuration of lines, and it is easy to see that all of these have even length: your first argument therefore can handle the general situation with a little extra work. –  Mariano Suárez-Alvarez Mar 20 '12 at 23:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.