頂点が 個の単純無向グラフ があり、次数が の頂点がちょうど 個、次数が の頂点がちょうど 個ある（これで 個の頂点すべてである）。 の辺の本数を求めよ。
グラフの次数と握手補題
頂点集合・辺集合で与えられたグラフや , などの標準的なグラフについて、各頂点の次数と辺の数を求められる。握手補題 を使って、辺数や奇数次の頂点の個数を求められる
前提
- 組合せ （数学A 場合の数と確率）
この技能までの道筋（5 技能）
読み込み中…
右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。
一覧で見る（前提が先）
- 樹形図で数え上げる （算数 場合の数）
- 積の法則と和の法則 （算数 場合の数）
- 和の法則・積の法則と樹形図 （数学A 場合の数と確率）
- 順列・円順列・重複順列 （数学A 場合の数と確率）
- 組合せ （数学A 場合の数と確率）
説明
グラフの各頂点に「何本の辺が出ているか」を表す数を次数といいます。この技能を使うと、頂点集合・辺集合で与えられたグラフや完全グラフ 、完全二部グラフ について、次数と辺の数を求められます。さらに握手補題 を使えば、辺を 1 本ずつ数えなくても次数の合計から辺の数がわかります。奇数次の頂点が何個ありうるかを判定するときにも使います。
なぜそうしてよいのか
ここでのグラフは、頂点の集合 と、異なる 2 頂点を結ぶ辺の集合 からなるもの（同じ 2 頂点を結ぶ辺は 1 本まで、頂点から自分自身へ戻る辺はなし）とします。頂点 の次数 は、 を端点にもつ辺の本数です。 個の頂点のどの 2 つも辺で結ばれたグラフを完全グラフ といいます。頂点が 個の組 と 個の組 に分かれていて、 の頂点と の頂点の組すべてが辺で結ばれ、同じ組どうしは結ばれていないグラフを完全二部グラフ といいます。
握手補題の理由は「同じものを 2 通りに数える」ことです。(頂点, その頂点を端点にもつ辺) という組の個数を数えます。頂点ごとに数えると、頂点 からは 個の組ができるので、合計は です。辺ごとに数えると、どの辺もちょうど 2 つの端点をもつので 1 本につき 2 個、合計は です。同じ個数なので が成り立ちます。パーティーで握手をすると、1 回の握手で 2 人が「握手した回数」を 1 ずつ増やすのと同じです。
ここから、次数の合計は必ず偶数になります。偶数次の頂点の次数の和は偶数なので、奇数次の頂点の次数の和も偶数でなければならず、奇数を足して偶数になるには奇数が偶数個必要です。よって奇数次の頂点の個数は必ず偶数です。
手順
グラフの頂点と辺の結び方を確認する（辺集合が書かれていれば、各辺 の両端を把握する。 や なら定義を思い出す）。
各頂点の次数を求める。辺集合が書かれていれば、その頂点が現れる辺の本数を数える。 では各頂点は自分以外の全頂点と結ばれるので 。 では 側の頂点の次数は 、 側の頂点の次数は 。
次数をすべて足して を計算する。
握手補題 を使い、 として辺の数を求める（奇数次の頂点の個数を問われたら、次数の和が偶数になることを使う）。
可能なら別の方法（例えば なら ）で検算する。
例題
完全グラフ の各頂点の次数と、握手補題を用いて辺の数を求めよ。答えとして辺の数を求めよ。
例題の解答
手順1: は 10 個の頂点のどの 2 つも 1 本の辺で結ばれたグラフである。
手順2: 各頂点は自分以外の 9 個の頂点と結ばれているので、すべての頂点について 。
手順3: 次数の合計は 。
手順4: 握手補題 より 、よって 。
手順5: 検算。辺は 10 頂点から 2 頂点を選ぶごとに 1 本あるので となり一致する。
したがって辺の数は 。
答え:
よくある誤り
次数の合計をそのまま辺の数としてしまう誤り。各辺は 2 つの端点で 2 回数えられているので、正しくは 。例えば では ではなく 。
の各頂点の次数を としてしまう誤り。自分自身とは結ばれないので、正しくは （ なら 9）。
の辺の数を としてしまう誤り。同じ組どうしは結ばれないので、正しくは 側 頂点がそれぞれ次数 をもち、 側 頂点がそれぞれ次数 をもつから （ なら ではなく ）。
次数が奇数の頂点が奇数個あるグラフが作れると考えてしまう誤り。例えば次数の並びが だと和が で奇数となり に等しくなれないので、そのようなグラフは存在しない。正しくは奇数次の頂点の個数は必ず偶数。
この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。
入口の問題
個の頂点からなる完全グラフを とする。 は、相異なる 頂点がどれもちょうど 本の辺で結ばれている単純無向グラフである。各頂点の次数と握手補題 を用いて、 の辺の本数 を求めよ（答えるのは辺の本数 だけでよい）。
正二十面体の頂点と辺を、そのまま頂点と辺とする単純無向グラフ （正二十面体グラフ）を考える。 の頂点は 個である。正二十面体の各頂点には 本の辺が集まっているので、 のどの頂点の次数も である。握手補題を用いて、 の辺の数を求めよ。
この技能を使う問題
整数 は を満たすとする。完全 2 部グラフ （単純グラフ）が「オイラー閉路をもつ」または「ハミルトン閉路をもつ」の少なくとも一方を満たすような組 の個数を求めよ。
ここで、オイラー閉路とはすべての辺をちょうど 1 回ずつ通って出発点に戻る閉じた道のことであり、ハミルトン閉路とはすべての頂点をちょうど 1 回ずつ通って出発点に戻る閉路のことである。
正の整数 に対し、 を、 個の頂点からなる部集合と 個の頂点からなる部集合をもつ完全二部グラフとする。
ここでは、グラフのすべての辺をちょうど 1 回ずつ通る道（始点と終点は一致してもしなくてもよい）をオイラー路とよぶ。
をみたす整数の組 のうち、 がオイラー路をもつものは何組あるか。
頂点集合 と、次の 本の辺からなる辺集合 をもつ単純無向グラフ を考える。
の辺をいくつかの小道（同じ辺を 度通らない歩道）に分け、すべての辺がちょうど つの小道にちょうど 回ずつ含まれるようにしたい。必要な小道の本数の最小値を求めよ。ただし、小道は辺を 本以上含むものとし、始点と終点は一致してもしなくてもよい。頂点集合 と、次の 本の辺からなる辺集合 をもつ単純無向グラフ （車輪グラフ）を考える。
の彩色数 （隣接する 2 頂点が異なる色になるように頂点を塗るときの色の数の最小値）と、辺彩色数 （端点を共有する 2 辺が異なる色になるように辺を塗るときの色の数の最小値）を、組 の形でこの順に求めよ。頂点集合を とし、相異なる 2 頂点 を、一方が他方を割り切るときに限り辺で結んだ単純無向グラフを とする（たとえば は辺であり、 は辺ではない）。
のすべての辺を、どの 2 本の道も辺を共有しないような何本かの道に分ける。各辺はちょうど 1 本の道に含まれるようにする。ここで「道」とは、同じ辺を 2 度通らない歩道のことである。頂点は何度通ってもよく、始点と終点は一致してもしなくてもよい。
このように分けるとき、必要な道の本数の最小値を求めよ。
頂点集合を とし、相異なる 2 頂点 を、 を で割った余りが のいずれかであるときに限り辺で結んだ単純無向グラフを とする。言い換えると、 が辺で結ばれるのは または のときに限る。 の彩色数 （隣接する頂点が異なる色になるように頂点を塗るのに必要な色の最小数）と、辺彩色数 （端点を共有する辺が異なる色になるように辺を塗るのに必要な色の最小数）を、この順に組 で答えよ。
を頂点数 、辺数 の連結な単純グラフとし、 は平面に辺が交差しないように描かれている（平面グラフ）とする。この描画で平面が分けられてできる領域（外側の非有界な領域も含む）を面といい、その個数を とする。各面について、その境界をたどる閉路状の歩道の長さ（境界上の辺のうち、両側がともにその面であるものは 2 回数える）をその面の長さという。
のすべての頂点の次数が 以上であるとき、 には長さが 以下の面が少なくとも 1 つ存在することを証明せよ。
なお、連結な平面グラフに対するオイラーの公式 と、すべての面の長さの和が に等しいことは用いてよい。
を頂点数が 以上の有限な単純無向グラフとする。 の頂点彩色数（隣接する 2 頂点が異なる色になるように頂点を塗り分けるのに必要な色の最小数）を と書き、 とおく。頂点 の次数（ に隣接する頂点の個数）を と書く。
このとき、 には を満たす頂点 が少なくとも 個存在することを証明せよ。
を整数とする。頂点集合を とし、相異なる 2 頂点 を
のときに限り辺で結んだ単純無向グラフを とする（閉路 の 2 乗グラフ）。 の彩色数（隣接する頂点が異なる色になるように頂点を塗るのに必要な最小の色数）を 、辺彩色数（同じ頂点を端点にもつ辺が異なる色になるように辺を塗るのに必要な最小の色数）を とする。
の値を求めよ。頂点集合 と、次の 本の辺からなる単純無向グラフ を考える。
で隣接していない相異なる 頂点の組 に対し、 に辺 を 本加えた単純グラフを と書く。ここで、オイラー路とはすべての辺をちょうど 回ずつ通る道（始点と終点は一致してもしなくてもよい）であり、ハミルトン閉路とはすべての頂点をちょうど 回ずつ通る閉路である。
隣接していない 頂点の組 のうち、
- がオイラー路をもつものの個数を 、
- がハミルトン閉路をもつものの個数を 、
- がオイラー路とハミルトン閉路の両方をもつものの個数をとする。組 をこの順に求めよ。
集合 の 3 元部分集合全体を頂点集合とし、2 つの頂点（3 元部分集合） を のときに限り辺で結んだ単純グラフ（クネーザーグラフ ）を とする。 の彩色数 と辺彩色数 をこの順に求めよ。
頂点集合を とし、相異なる 2 頂点 を、 のときに限り辺で結んだ単純グラフを とする（ は長さ の閉路 の補グラフである）。
の彩色数（隣り合う頂点が異なる色になるように頂点を塗るのに必要な色の数の最小値）を 、辺彩色数（端点を共有する辺が異なる色になるように辺を塗るのに必要な色の数の最小値）を とする。組 をこの順に求めよ。
各部集合がちょうど 個の頂点からなる完全 部グラフを とする。すなわち は、頂点集合 （ は互いに素で、それぞれ 個の頂点からなる）をもち、異なる部集合に属する 2 頂点はすべて辺で結ばれ、同じ部集合に属する 2 頂点は辺で結ばれない単純グラフである。
の彩色数 と辺彩色数 を求め、組 の形で答えよ。ここで辺彩色数とは、端点を共有する 2 辺が異なる色になるように全ての辺を塗るのに必要な色の数の最小値である。
を、 個の頂点からなる部集合 と 個の頂点からなる部集合 をもつ完全二部グラフ（ の各頂点と の各頂点がちょうど 1 本の辺で結ばれ、それ以外に辺はない単純グラフ）とする。
を平面に描く。ただし、頂点は相異なる点、辺はその両端点を結ぶ連続曲線で表し、辺は自分の端点以外の頂点を通らず、2 本の辺は有限個の点でしか交わらず、3 本以上の辺が同じ 1 点（端点以外）で交わることはないものとする。このような描き方において、2 本の辺が端点以外で交わる点の個数を交差数とよぶ（同じ 2 本の辺が何点で交わっても、交わる点を 1 点ずつ数える）。
のすべての描き方にわたる交差数の最小値を求めよ。
頂点集合を とし、相異なる 2 頂点 を のときに限り辺で結んだ単純無向グラフを とする（ 行 列の格子グラフ）。各辺の長さを とする。
のある頂点から出発して の辺をたどり、出発した頂点に戻ってくる閉じた歩道で、 のすべての辺を少なくとも 1 回ずつ通るものを考える（同じ辺や同じ頂点を何度通ってもよい）。このような閉じた歩道の長さ（通った辺の本数を、重複も含めて数えたもの）の最小値を求めよ。
この技能の次に学べること
- 行列木定理による全域木の個数 （大学数学 離散数学・組合せ論）
- オイラー路・オイラー閉路の判定 （大学数学 グラフ理論）
- 2 部グラフと奇閉路 （大学数学 グラフ理論）
- 最大独立集合と最小頂点被覆 （大学数学 グラフ理論）
- 最小全域木（クラスカル法・プリム法） （大学数学 グラフ理論）
- ネットワークと s-t カットの容量 （大学数学 グラフ理論）