頂点集合を とし、辺集合 を次の 本の辺からなるものとする単純無向グラフ を考える（ は完全グラフ から辺 を除いたグラフである）。
の辺彩色数 を求めよ。ただし、辺彩色とは、共通の端点をもつ 2 本の辺が異なる色になるように各辺に色を塗ることであり、辺彩色数とはそれに必要な色の数の最小値である。
辺彩色数とヴィジングの定理
辺彩色数 を、次の評価を使って求められる。ヴィジングの定理 、各色の辺がマッチングになることから得られる （頂点数が奇数の正則グラフでは ）、2 部グラフでの
前提
- 最大マッチングとケーニヒの定理 （大学数学 グラフ理論）
この技能までの道筋（9 技能）
読み込み中…
右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。
一覧で見る（前提が先）
- 樹形図で数え上げる （算数 場合の数）
- 積の法則と和の法則 （算数 場合の数）
- 和の法則・積の法則と樹形図 （数学A 場合の数と確率）
- 順列・円順列・重複順列 （数学A 場合の数と確率）
- 組合せ （数学A 場合の数と確率）
- グラフの次数と握手補題 （大学数学 グラフ理論）
- 2 部グラフと奇閉路 （大学数学 グラフ理論）
- 最大独立集合と最小頂点被覆 （大学数学 グラフ理論）
- 最大マッチングとケーニヒの定理 （大学数学 グラフ理論）
説明
グラフの辺に色を塗るとき、1 つの頂点に集まる辺どうしは必ず違う色にするという決まりを置きます。このとき必要な色の最小数を辺彩色数 といいます。ヴィジングの定理 を使うと、答えは 2 通りに絞れます。そのうえで、マッチングの大きさや 2 部グラフかどうかを手がかりに、どちらになるかを決めます。時間割の作成（同じ人が同時に 2 つの予定に入らない）や、総当たり戦の日程づくりなどに使います。
なぜそうしてよいのか
多重辺もループもない単純グラフ を考え、最大次数を と書きます。次数 の頂点には 本の辺が集まり、そのどの 2 本も端点を共有します。そのため、これらの辺はすべて違う色にしなければならず、 です。逆向きの評価として、単純グラフなら 色で必ず塗り分けられる、というのがヴィジングの定理です。このページでは、この定理の証明は省略して定理として使います。参考までに述べると、証明は辺を 1 本ずつ塗り足していく方法をとります。そのとき、2 色が交互に並ぶ道で色を入れ替える操作だけでは足りません。ある頂点を中心にそこから出る辺の色を順にずらす操作（ファン）と組み合わせて、色を空けます。結論として、 は か のどちらかです。
どちらになるかを判定する道具の 1 つがマッチングです。同じ色の辺どうしは端点を共有しないので、1 色分の辺の集合はマッチングになり、その本数は 以下です。 色それぞれに 本以下の辺しかないので、 が成り立ちます。つまり です（辺が 1 本以上あるとき）。とくに、頂点数 が奇数で、すべての頂点の次数が のグラフ（-正則グラフ）を考えます。握手補題から です。マッチングの辺は 1 本につき頂点を 2 個使うので、 です。よって となり、ヴィジングの定理と合わせると と決まります。
2 部グラフでは になります（ケーニヒの辺彩色定理）。その証明の概略は次のとおりです。色を 個用意し、辺を 1 本ずつ塗っていきます。まだ塗っていない辺 について、 にはすでに塗った辺が 本以下しかありません。よって で使われていない色 があり、同様に で使われていない色 があります。 が でも使われていなければ、 を で塗れば済みます。そうでなければ、 から出発して、色 の辺、色 の辺、色 の辺、…と交互にたどれるだけたどった道 を考えます。各頂点で各色の辺は高々 1 本なので、この道は 1 通りに決まります。この が に到達することはありません。 には色 の辺がないので、 が に入るとすれば色 の辺を通ってきたことになります。 は色 の辺から始まるので、 の辺で到達するまでには偶数本の辺を通っています。すると、 の から までの部分に辺 を加えると、長さが奇数の閉路ができてしまいます。2 部グラフには奇閉路がないので、これは起こりえません。そこで 上の色 と色 を入れ替えます。入れ替えても正しい塗り分けのままで、 の辺の色は変わりません。一方、 では色 が空きます。こうして を で塗れるようになり、これを繰り返すと 色で全部の辺を塗れます。
手順
最大次数 を求め、下界 を書く。
単純グラフであることを確かめ、ヴィジングの定理から とする。これで答えは か に絞られる。
2 部グラフである（奇閉路がない）なら、 と結論する。
辺の本数 と、最大マッチングの大きさ を求める（ や増加道を使う）。 なら である。頂点数が奇数の正則グラフ（）は、つねにこの場合にあたる。
ここまでで決まらなければ、 色で実際に塗り分ける方法を探す。見つかれば 、 色では塗れないことを示せれば である。
例題
完全グラフ （5 個の頂点のどの 2 頂点も 1 本の辺で結ばれたグラフ）の辺彩色数 を求めよ。
例題の解答
手順 1： の各頂点は他の 4 頂点と結ばれているので である。よって 。
手順 2： は単純グラフなので、ヴィジングの定理より 。答えは 4 か 5 のどちらかである。
手順 3： は三角形（長さ 3 の奇閉路）を含むので、2 部グラフではない。この手順では決まらない。
手順 4：辺の本数は 。マッチングの辺は 1 本につき頂点を 2 個使い、頂点は 5 個しかないので、マッチングは 本以下である。頂点を とすると、辺 は 2 本のマッチングなので 。よって となる。これは、 が頂点数 5（奇数）の 4-正則グラフであることからもわかる。
以上から 。
答え:
よくある誤り
辺彩色数と頂点彩色数を取り違える誤り。たとえば の頂点彩色数が 4 であることから、 としてしまう。正しくは、 で、頂点を とすると の 3 色で塗り分けられる。よって 。
頂点数が奇数でありさえすれば になる、としてしまう誤り。正しくは正則であることも必要である。たとえば頂点数 5 の星 は 2 部グラフなので、 である。
下界 が に等しいときに、 と結論してしまう誤り。正しくは、これは下からの評価にすぎない。たとえばペテルセングラフでは だが、実際は である。また、 が整数でないときは切り上げる。
多重辺のあるグラフにもヴィジングの定理 を使ってしまう誤り。正しくは、この定理は単純グラフについてのものである。たとえば 3 頂点の各 2 頂点を 2 本ずつの辺で結んだグラフでは である。しかし 6 本の辺のどの 2 本も端点を共有するので、 となる。
この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。
入口の問題
頂点集合 と、次の 本の辺からなる辺集合 をもつ単純無向グラフ を考える。
同じ頂点を端点にもつ辺どうしが異なる色になるように辺を塗り分けるとき、必要な色の数の最小値（辺彩色数） を求めよ。頂点集合 と、次の 本の辺からなる辺集合 をもつ単純無向グラフ を考える。
（ は完全グラフ から辺 を 1 本だけ取り除いたグラフである。）
の辺彩色数 を求めよ。ただし、辺彩色とは、端点を共有する 2 辺が必ず異なる色になるように各辺に色を塗ることであり、 はそのような彩色に必要な色の数の最小値である。
この技能を使う問題
頂点集合 と、次の 本の辺からなる辺集合 をもつ単純無向グラフ （車輪グラフ）を考える。
の彩色数 （隣接する 2 頂点が異なる色になるように頂点を塗るときの色の数の最小値）と、辺彩色数 （端点を共有する 2 辺が異なる色になるように辺を塗るときの色の数の最小値）を、組 の形でこの順に求めよ。頂点集合を とし、相異なる 2 頂点 を、 を で割った余りが のいずれかであるときに限り辺で結んだ単純無向グラフを とする。言い換えると、 が辺で結ばれるのは または のときに限る。 の彩色数 （隣接する頂点が異なる色になるように頂点を塗るのに必要な色の最小数）と、辺彩色数 （端点を共有する辺が異なる色になるように辺を塗るのに必要な色の最小数）を、この順に組 で答えよ。
を整数とする。頂点集合を とし、相異なる 2 頂点 を
のときに限り辺で結んだ単純無向グラフを とする（閉路 の 2 乗グラフ）。 の彩色数（隣接する頂点が異なる色になるように頂点を塗るのに必要な最小の色数）を 、辺彩色数（同じ頂点を端点にもつ辺が異なる色になるように辺を塗るのに必要な最小の色数）を とする。
の値を求めよ。集合 の 3 元部分集合全体を頂点集合とし、2 つの頂点（3 元部分集合） を のときに限り辺で結んだ単純グラフ（クネーザーグラフ ）を とする。 の彩色数 と辺彩色数 をこの順に求めよ。
頂点集合を とし、相異なる 2 頂点 を、 のときに限り辺で結んだ単純グラフを とする（ は長さ の閉路 の補グラフである）。
の彩色数（隣り合う頂点が異なる色になるように頂点を塗るのに必要な色の数の最小値）を 、辺彩色数（端点を共有する辺が異なる色になるように辺を塗るのに必要な色の数の最小値）を とする。組 をこの順に求めよ。
各部集合がちょうど 個の頂点からなる完全 部グラフを とする。すなわち は、頂点集合 （ は互いに素で、それぞれ 個の頂点からなる）をもち、異なる部集合に属する 2 頂点はすべて辺で結ばれ、同じ部集合に属する 2 頂点は辺で結ばれない単純グラフである。
の彩色数 と辺彩色数 を求め、組 の形で答えよ。ここで辺彩色数とは、端点を共有する 2 辺が異なる色になるように全ての辺を塗るのに必要な色の数の最小値である。