Simplicity

There is something extremely awesome about simplicity. A problem should not be considered solved unless a simple solution is obtained.
Here is one such problem that was given us during my graph theory course. It is on graph coloring.
X(G) represents the chromatic number of the graph.

Question: Given a set of lines in the plane with no three meeting at a point, form a graph G whose vertices are the intersections of the lines, with two vertices adjacent if they appear consecutively on one of the lines. Prove that X(G) =< 3.

I pondered this for a long time applying theorems and making no headway. Finally an elegant and simple solution came to me. Even now I remember the contentment this solution gave me. As expected, it was much simpler than the one the professor offered in the tutorial session.

Solution: Assume some co-ordinate axis system, so that each vertex of the graph has a (x,y) co-ordinate.
Use the following algorithm:
1. Start coloring from the left, i.e. start coloring vertices according to increasing value of x- co-ordinate.
2. If two or more vertices have same x co-ordinate value, first color the one with lowest value of y - co-ordinate.
Its now immediate that while coloring any vertex, atmost two of its neighbors can be already colored and hence X(G) =< 3.
------------

I definitely wasn't the most brilliant student of the lot - far from it actually... but simple solutions do come unexpectedly, and they can come to anyone I guess.

I still remember sitting still for a long time afterwards.. savoring the beauty of this simple solution...