Colour the edges of each Eulerian circuit alternately blue, green, blue, green, …
詳しい解説
G の各連結成分はすべての次数が4、すなわち偶数であるから、その成分のすべての辺をちょうど1回ずつ使うオイラー閉路を持つ。m 個の頂点を持つ成分はその閉路に 2m 本、すなわち偶数本の辺を提供する。閉路の辺を通過する順に青、緑、青、緑、と塗っていく。長さが偶数なので、最後の辺と最初の辺は異なる色になり、交互の塗り分けは閉路全体で一貫する。