競技数学：グラフ・離散構造 | 雑多な話題

1 最初に仕様を固定する

記事や解答では、次を必ず明示します。

頂点は何を表すか
辺はどの関係を表すか
辺に向きがあるか
同じ2頂点を結ぶ辺を重複して許すか
頂点から自分自身へのループを許すか

本記事では、特に断らない限り有限単純無向グラフを扱います。頂点は有限個、辺に向きや重複はなく、ループもありません。

2 次数の総和

頂点 $v$ に接続する辺の本数を次数 $d(v)$ とします。すべての頂点の次数を足すと、各辺が両端で2回数えられるので

$\sum_{v}d(v)=2|E|$

です。これを握手補題と呼びます。特に、奇数次数の頂点の個数は偶数です。

3 例1：知り合いの人数

5人の集団で、各人の知り合いの人数がすべて異なることはないことを示します。人を頂点、知り合い関係を辺とします。次数は0から4の5種類です。

もし5人の次数がすべて異なるなら、次数は $0,1,2,3,4$ の全部です。しかし次数4の人がいると、全員がその人の知り合いなので、次数0の人は存在できません。矛盾です。したがって同じ次数の人が2人います。

これは単純な鳩の巣原理ですが、次数の最大値と最小値が同時には現れないというグラフの制約を使っています。

4 例2：彩色と二部グラフ

頂点を赤と青の2色に分け、同じ色の頂点同士を辺で結ばないようにできるグラフを二部グラフといいます。すべての閉路が偶数長、同値に奇閉路を含まないなら、各連結成分で始点を赤、隣を青と交互に塗れます。道そのものの長さは奇数でも構いません。

一方、奇閉路は二部グラフではありません。奇閉路を一周すると、交互に塗った最後の頂点が始点と同じ色になるべきなのに、辺で結ばれてしまうからです。これは彩色による不可能性証明の基本です。

5 例3：三角形を含まないグラフの辺数

頂点数 $n$ の単純グラフが三角形を含まないなら、辺数 $m$ は

$m\le \left\lfloor\frac{n^2}{4}\right\rfloor$

を満たすことを示します。

辺 $uv$ の両端の次数を $d(u),d(v)$ とします。もし $d(u)+d(v)>n$ なら、 $u$ と $v$ の共通の隣接頂点が存在します。実際、 $u$ の隣接頂点と $v$ の隣接頂点を合わせると、重複なしでは $d(u)+d(v)$ 個ありますが、 $u,v$ 自身を除く $n-2$ 個程度しか置けず、したがって共通点が生じます。その共通点と $u,v$ が三角形を作るので、三角形がない仮定から

$d(u)+d(v)\le n$

です。

これを全辺について足すと、各頂点の次数は $d(v)$ 回現れるため

$\sum_{uv\in E}(d(u)+d(v))=\sum_v d(v)^2\le mn.$

コーシー・シュワルツの不等式より

$\sum_vd(v)^2\ge \frac{(\sum_vd(v))^2}{n}=\frac{(2m)^2}{n}.$

したがって $4m^2/n\le mn$ 、 $m\le n^2/4$ 。整数なので主張が得られます。 $n$ が偶数で、頂点を2つの同人数の組に分け、組内に辺を置かない完全二部グラフでは等号になります。

この問題では、グラフ化、次数の総和、不等式、等号構成が一続きになっています。

6 競技問題での翻訳

「互いに関係がある」：辺を置く。
「関係がない」：補グラフの辺を考える。
「同時に選べない」：独立集合や彩色へ翻訳する。
「全員が何人かと関係する」：最小次数を評価する。
「最大の関係数」：辺数の極値問題にする。

図を描いたら、次数の総和、連結性、彩色、不変量のどれが使えるかを確認します。図を見て明らかに思えることも、最終解答では数式または論理で支えます。

7 演習

有限グラフの奇数次数の頂点数が偶数であることを握手補題から示せ。
6人の集団には、互いに知り合いである3人、または互いに知らない3人が必ず存在することを示せ。
三角形を含まない頂点数8のグラフの辺数の最大値を求め、等号を与えるグラフを構成せよ。
奇閉路を含まないグラフが二部グラフであることを、連結成分ごとに距離の偶奇で彩色して示せ。

2番は、1人を選んでその人との関係を赤・青に分け、鳩の巣原理を使うのが入口です。

§C5.5競技数学：グラフ・離散構造