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'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|improve this question
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.