1. 概要

無向単純グラフに対して，同じ頂点に接続する $2$ 辺が同じ色を持たないように，辺に色を割り当てることを辺彩色（edge coloring）といいます．辺彩色に必要な色数の最小値をそのグラフの辺彩色数（edge-chromatic number，chromatic index）といいます．

本記事では，完全グラフの辺彩色数を求めることを目標とします．完全グラフの辺彩色は，総当たり戦のスケジューリング等の問題にも応用されます．

2. 前提知識

完全グラフや辺彩色などの，グラフ理論の用語を仮定します．必要に応じてグラフ理論用語集を参照してください．

3. 奇数頂点完全グラフの辺彩色数

【定理 1】

$N$ を正の奇数とするとき，$N$ 頂点完全グラフの辺彩色数は，$N=1$ ならば $0$，$N\geq 3$ ならば $N$ である．

$N=1$ の場合は明らかです．以下 $N\geq 3$ を仮定します．

$G$ を $N$ 頂点の完全グラフとします．証明するべきことは次の $2$ つです．

$G$ の任意の辺彩色について，色数が $N$ 以上である．
$G$ を $N$ 個の色で辺彩色をすることが可能である．

$G$ の任意の辺彩色について，色数が $N$ 以上であることを示します．$G$ の辺彩色において，ある色 $c$ の辺の個数を $n_c$ とすれば，$2n_c\leq N$ です．これは，辺の端点が同じ色の辺について重複しないからです．さらに $N$ が奇数であることから $n_c\leq \frac{N-1}{2}$ です．

一方で，$G$ には辺が $\frac{N(N-1)}{2}$ 個あります．したがってすべての辺に色を割り当てるには，少なくとも

$$\frac{N(N-1)}{2}\div \frac{N-1}{2}=N$$

個以上の色が必要です（この除算において $N\geq 3$ を用いました）．以上で $G$ の任意の辺彩色について，色数が $N$ 以上であることが示されました．

次に $G$ を $N$ 個の色で辺彩色をすることが可能であることを示します．これは例えば，次のような方法によって可能です．

$G$ の頂点に適当に $0, 1, 2, \ldots, N-1$ の番号をつける．
$0, 1, 2, \ldots, N-1$ の $N$ 個の色を用いる．頂点 $u, v$ を結ぶ辺を色 $(u+v)\bmod N$ で塗る．

これが辺彩色になっていることを確かめるには同じ頂点に接続する $2$ つの辺の色が異なることを示せばよいですが，$u$ に隣接する頂点 $v_1,v_2$ について

$$u+v_1\equiv u+v_2\pmod{N}\implies v_1\equiv v_2\pmod{N}\implies v_1=v_2$$

により示されます． $\blacksquare$

3.1. 図解

$N$ 頂点完全グラフを正 $N$ 角形の頂点とそれらを結ぶ線分として図示した場合，上の証明での構成は，平行な線分を同じ色でまとめるという形で図示することができます．

また，$2$ 行に頂点を並べて上下に並ぶ頂点を対にするという図示も有名です．この場合，$2$ 行に頂点を並べて（ただし $1$ 箇所に空マスができる），頂点の並び順を適切に回転していくことで，各色の辺を得ることができます．

4. 偶数頂点完全グラフの辺彩色数

【定理 2】

$N$ を正の偶数とするとき，$N$ 頂点完全グラフの辺彩色数は $N - 1$ である．

$N=2$ の場合は明らかです．以下 $N\geq 4$ を仮定します．

$G$ を $N$ 頂点の完全グラフとします．証明するべきことは次の $2$ つです．

$G$ の任意の辺彩色について，色数が $N-1$ 以上である．
$G$ を $N-1$ 個の色で辺彩色をすることが可能である．

$G$ の任意の辺彩色について，色数が $N-1$ 以上であることは，$N$ が奇数の場合と同様に証明できます．あるいは，任意の頂点の次数が $N-1$ であり，$1$ つの頂点に接続する辺はすべて異なる色でなければならないことからも明らかです．

次に $G$ を $N-1$ 個の色で辺彩色をすることが可能であることを示します．これは例えば，次のような方法によって可能です．

$G$ の頂点に適当に $0, 1, 2, \ldots, N-1$ の番号をつける．
まず，$G$ のうち $N-1$ 頂点 $0, 1, 2, \ldots, N-2$ について，それらを結ぶ辺を【定理 1】で示したように $N-1$ 色で彩色する．
するとどの色 $c$ についてもちょうどひとつ，その色の辺と接続していないような頂点（番号が $N-2$ 以下）ができる．この頂点と頂点 $N-1$ を色 $c$ で結ぶ．

$\blacksquare$

4.1. 図解

例えば正 $(N-1)$ 角形の中心に新しく頂点を足すと，次のような図示が得られます．

$2$ 行に頂点を並べて回転していくという図示も可能です．この場合，位置を固定する特別な頂点を用意して，それ以外の頂点を回転させます．

ひとつの頂点で対称性を崩すのがポイントで，盲点になりやすい構成方法だと思います．

5. 応用例：総当たり戦のスケジューリング

次のような問題を考えてみましょう．

【問題 3】

$N$ を $2$ 以上の整数とします．$N$ 人の選手が総当たり戦を行います．$1$ 回のラウンドごとに，いくつかの試合を並行して行うことができます．ただし，同じラウンド内で同じ選手が行える試合は $1$ 試合までであるとします．総当たり戦が完了する，つまり任意の $2$ 人が試合を行うまでにかかるラウンド数の最小値はいくつでしょうか？

この問題は，$2$ 人組に対して試合を行うラウンドを色と見なすことで，完全グラフの辺彩色の問題と見なすことができます．したがって答は，

$N$ が奇数ならば $N$．
$N$ が偶数ならば $N-1$．

となります．この問題に対する本記事で述べた解法は有名で，実際のスポーツなどの競技でも実用されているそうです．

6. 関連問題

問題へのコメント

1 はほとんどそのまま，完全グラフの辺彩色を出力する問題です．
2, 3 は少し工夫が必要になりますが，完全グラフの辺彩色の知識があるとかなり解きやすくなると思います．
4 は完全グラフの辺彩色に近い問題設定の難問です．

7. まとめ

本記事では，完全グラフの辺彩色数について解説しました．

辺彩色数については，他にも Vizing の定理や二部グラフに関する König の定理など有名な結果があります．また完全グラフの辺集合の分割については，ハミルトンサイクルへの分割や三角形の分割など他にも有名問題が知られています．

8. 参考文献

Wikipedia．Round-robin tournament．https://en.wikipedia.org/wiki/Round-robin_tournament．（閲覧日: 2026-03-05）．
Wikipedia．Graph factorization．https://en.wikipedia.org/wiki/Graph_factorization．（閲覧日: 2026-03-05）．
Wikipedia．Edge coloring．https://en.wikipedia.org/wiki/Edge_coloring．（閲覧日: 2026-03-05）．

トップページ：AtCoder Algorithm Lectures