Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm attempting to prove the following proposition:

For n>2 lines arranged in the plane, in general position, it is possible to color the vertices of the lines with 3 colors such that no 2 adjacent vertices have the same color.

I've been trying to prove via induction, but can't seem to get beyond the following thoughts:

  1. Obviously we start with a base case of n=3 and (trivially) prove it can be colored.
  2. We could, when given n lines, subtract one and accept that for n-1 it is true. But I'm unable to find how to prove that n is true from n-1 being true.

Would graph theory be helpful here?

share|cite|improve this question

Your Answer


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

Browse other questions tagged or ask your own question.