Heard from Adnan Aziz in 1996. He had heard it from a friend who had heard it from Edsger Dijkstra.

_{i} and y_{j} iff there is a point in the corresponding place. If G has a cycle (it must be an even cycle), we color the edges alternatively and remove those edges. When this procedure can no longer be applied, we must be left with a tree. At this point, we can solve the problem by induction on the number of edges as follows: remove e a leaf edge, color the remaining edges balanced, now look at the parent of that leaf and choose the right color for e to maintain the induction hypothesis.

© Copyright 2008—2017, Gurmeet Manku.