中国人郵便配達問題
グラフ理論において、グラフ中のすべての辺を1度ずつ通るような閉路が存在するグラフを「オイラーグラフ」といい、その閉路を「オイラー路」という。よってこの問題を解くには、与えられたグラフにおいて、グラフ中の一部の辺を2本に増やすことで、オイラーグラフが得られるようにすることを考えればよい。そのような辺の組み合わせは一般に複数通りあるため、その中で増やした辺に割り当てられた距離が最小になるような辺の組み合わせを求めることになる。
オイラーグラフの特徴として「すべての頂点の次数(頂点に接続する辺の数)は偶数である」ことが挙げられる。一般の(次数が奇数である頂点を持ちうる)グラフに対しては、以下の方法に基づいてグラフ中の一部の辺を2本に増やせばオイラーグラフになる。
グラフ中に存在する、次数が奇数であるすべての頂点を集める。なおその頂点数は「握手補題」により必ず偶数個になる。
上記の頂点を適当に二つずつ組み合わせる。