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 2 of 6: Turn colours into a 4-regular graph
In plain words
Collapsing each colour to a single vertex turns the strings into edges of a graph, and counting incidences shows every vertex has the same degree.
Detailed analysis
Group the 4n pebbles into n boxes by colour, four pebbles per box, and let G be the multigraph whose vertices are the boxes and whose edges are the 2n strings, a string joining two pebbles of the same colour becoming a loop worth 2 at that vertex. Since a box holds exactly 4 pebbles and each pebble is an endpoint of exactly one string, every vertex of G has degree exactly 4, and G has 2n edges on n vertices.