Problem 3
There are pebbles of weights . Each pebble is colored in one of colors and there are four pebbles of each color. Show that we can arrange the pebbles into two piles so that the following two conditions are both satisfied:
- The total weights of both piles are the same.
- Each pile contains two pebbles of each color.
Step 3 of 6: Two-colour the edges via Eulerian circuits
In plain words
Even degree everywhere means each piece of the graph can be traced in one closed walk, and alternating colours along that walk is the natural way to split it evenly.
Detailed analysis
Every connected component of G has all degrees equal to 4, hence even, so it admits an Eulerian circuit that uses every edge of the component exactly once; a component with m vertices contributes 2m edges to its circuit, an even number. Colour the edges of the circuit blue, green, blue, green, and so on in the order they are traversed; because the length is even, the last edge and the first edge receive different colours, so the alternation is consistent all the way around.