連結成分の全頂点の次数が偶数ならオイラー閉路があり、連続する辺を交互に彩色できる。
全頂点の次数が偶数の連結成分ではオイラー閉路をとる。二部グラフなので閉路の長さは偶数である。その辺を赤白交互に塗る。各頂点では入る辺と出る辺が同色一組ずつになり、差は 000 である。