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

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.