MathLabs

Problem 3

There are 4n4n pebbles of weights 1,2,3,…,4n1, 2, 3, \ldots, 4n. Each pebble is colored in one of nn 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 4 of 6: Check the local balance at each vertex
Previous stepNext step
In plain words

Strict alternation forces the two edges meeting at each pass through a vertex to differ in colour, and a degree-4 vertex is passed through exactly twice.

deg⁡blue(v)=deg⁡green(v)=2 for every vertex v.\deg_{\text{blue}}(v)=\deg_{\text{green}}(v)=2\ \text{for every vertex}\ v.
Detailed analysis

A vertex of degree 4 is encountered twice by the Eulerian circuit. If a visit is an ordinary passage, the incoming and outgoing edges have opposite colours, so that passage contributes one blue and one green incidence. If a visit traverses a loop, the loop contributes two incidences of its single colour; the two incidences adjacent to that loop in the cyclic tour have the opposite colour (and if there are two loops, their colours alternate). In every case, counting the four incidences of the vertex gives exactly two blue and two green edges.