中国人郵便配達問題
与えられたグラフGがオイラーグラフである場合は、求める閉路の長さはGの辺の距離の総和である(そのオイラー路自体が条件を満たしている)。
与えられたグラフGが木である場合には、すべての辺を2本に増やさなければならず、求める閉路の長さはGの辺の距離の総和の2倍である。