奇次数頂点が 2k2k2k 個ある連結グラフは kkk 本の道に分解でき、二部性により各道は二部を交互に通る。
成分に 2k>02k>02k>0 個の奇次数頂点があれば、標準的な道分解定理により辺を互いに素な kkk 本の道（trail）に分ける。各道の辺を赤白交互に彩色する。道の内部頂点では各色一辺ずつが対になり、端点では一辺だけ余る。全ての道を合わせても各頂点の差は高々 111 である。