オイラー路・オイラー閉路の判定

連結グラフがオイラー閉路をもつ条件（すべての次数が偶数）と、オイラー路をもつ条件（奇数次の頂点が 0 個または 2 個）を使って、 $K_{m, n}$ などがオイラー路・オイラー閉路をもつかを判定できる

前提

グラフの次数と握手補題（大学数学グラフ理論）

この技能までの道筋（6 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
グラフの次数と握手補題（大学数学グラフ理論）

説明

グラフのすべての辺をちょうど 1 回ずつ通る道筋（一筆書き）が存在するかを、各頂点の次数を数えるだけで判定できるようになります。実際に道筋を探さなくても、奇数次の頂点の個数で答えが決まります。 $K_{n}$ や $K_{m, n}$ のように頂点や辺が多いグラフや、 $m, n$ を文字のまま含むグラフでも、すぐに判定できます。

なぜそうしてよいのか

用語を決めます。グラフのすべての辺をちょうど 1 回ずつ通る道筋（同じ頂点は何度通ってもよい）をオイラー路といいます。そのうち出発点と終点が同じものをオイラー閉路といいます。このページでは、閉じたものもオイラー路に含めます。判定には次の事実を使います。孤立点（次数 0 の頂点）を除いて連結なグラフでは、次の 2 つが成り立ちます。(1) オイラー閉路をもつのは、すべての頂点の次数が偶数のとき、かつそのときに限る。(2) オイラー路をもつのは、奇数次の頂点が 0 個または 2 個のとき、かつそのときに限る。2 個のときは、その 2 頂点が始点と終点になります。

次数の条件が必要な理由: 道筋が途中の頂点を 1 回通過するたびに、「入る辺」と「出る辺」の 2 本を使います。そのため、始点と終点以外の頂点の次数は偶数です。閉路なら、始点（＝終点）も「最初に出る辺」と「最後に入る辺」が組になるので偶数です。開いた道なら、奇数になりうるのは始点と終点の 2 つだけです。なお握手補題 $\sum_{v} de g v = 2∣ E ∣$ より、次数の和は偶数です。したがって奇数次の頂点はいつも偶数個で、1 個や 3 個になることはありません。

条件が十分な理由（直観）: すべての次数が偶数だとします。ある頂点から未使用の辺をたどり続けると、途中の頂点に入ったときは、入った辺の相手となる出る辺が必ず残っています。そのため、行き詰まるのは出発点に戻ったときだけで、閉路が 1 つできます。まだ使っていない辺が残っていれば、グラフが連結なので、その閉路上に未使用の辺が出ている頂点があります。そこから同じように閉路を作り、元の閉路に差し込みます。これを繰り返すと、全部の辺を使う閉路になります。奇数次の頂点が 2 個 $u, v$ の場合は、 $u$ と $v$ を結ぶ辺を 1 本仮に加えます（多重辺になってもかまいません）。するとすべての次数が偶数になるので、オイラー閉路ができます。そこから仮の辺を取り除けば、 $u$ から $v$ へのオイラー路が残ります。

手順

グラフが（孤立点を除いて）連結であることを確かめる。連結でなければ、オイラー路もオイラー閉路もない（辺が 2 つ以上の成分に分かれているとき）。
各頂点の次数を求める。例えば $K_{m, n}$ （ $m$ 個の頂点の組と $n$ 個の頂点の組の間をすべて辺で結んだグラフ）では、 $m$ 個の側の頂点の次数は $n$ 、 $n$ 個の側の頂点の次数は $m$ になる。
奇数次の頂点の個数 $k$ を数える（握手補題より $k$ は必ず偶数になる）。
$k$ の値で判定する。 $k = 0$ ならオイラー閉路をもつ（オイラー路ももつ）。 $k = 2$ ならオイラー路をもつが、オイラー閉路はもたない（始点と終点は奇数次の 2 頂点）。 $k \geq 4$ ならどちらももたない。

例題

$1 \leq n \leq 10$ を満たす整数 $n$ のうち、完全二部グラフ $K_{3, n}$ がオイラー路（閉じたものも含む）をもつような $n$ をすべて求めよ。

例題の解答

手順1（連結性）: $n \geq 1$ なので、 $K_{3, n}$ では 3 個側のどの頂点も $n$ 個側のすべての頂点と辺で結ばれています。よって連結です。

手順2（次数）: 3 個側の 3 頂点の次数はそれぞれ $n$ です。 $n$ 個側の $n$ 頂点の次数はそれぞれ $3$ です。

手順3（奇数次の頂点を数える）:
- $n$ が奇数のとき: 3 個側の 3 頂点（次数 $n$ ）も、 $n$ 個側の $n$ 頂点（次数 3）もすべて奇数次です。よって $k = n + 3 \geq 4$ です。
- $n$ が偶数のとき: 3 個側は偶数次です。 $n$ 個側の $n$ 頂点は次数 3 で奇数次なので、 $k = n$ です。

手順4（判定）: オイラー路をもつのは $k = 0$ または $k = 2$ のときです。 $n$ が奇数なら $k \geq 4$ なので、もちません。 $n$ が偶数なら $k = n$ で、 $n \geq 2$ だから $k = 0$ にはならず、 $k = 2$ となるのは $n = 2$ のときだけです。

$n = 2$ のとき、 $K_{3, 2}$ の奇数次の頂点は 2 個側の 2 頂点（次数 3）です。この 2 頂点を始点・終点とするオイラー路があります（閉路ではありません）。

よって求める $n$ は $n = 2$ のみです。

答え: ${2}$

よくある誤り

連結性を確かめずに、次数だけで判定してしまう誤り。例えば三角形 2 つを離して並べたグラフは、全頂点の次数が $2$ （偶数）ですが、オイラー閉路はありません。正しくは、まず（孤立点を除いて）連結であることを確認してから次数の条件を使います。
奇数次の頂点が 2 個のときもオイラー閉路があるとしてしまう誤り。閉路ではすべての頂点で入る辺と出る辺が組になるので、全頂点の次数が偶数でなければなりません。正しくは、 $k = 2$ ならオイラー路はあるが閉路はなく、始点と終点は奇数次の 2 頂点に限られます。
$K_{m, n}$ の次数を取り違え、 $m$ 個側の頂点の次数を $m$ としてしまう誤り。 $m$ 個側の各頂点は反対側の $n$ 個すべてと結ばれるので、正しくは次数 $n$ です。例えば $K_{2, 3}$ では、2 個側の頂点の次数が $3$ 、3 個側の頂点の次数が $2$ です。
奇数次の頂点が 1 個や 3 個のグラフを想定してしまう誤り。握手補題 $\sum_{v} de g v = 2∣ E ∣$ より、奇数次の頂点の個数はいつも偶数です。数えた結果が奇数になったら、次数の計算を見直します。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

オイラー路・オイラー閉路の判定

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題