頂点が 個の単純無向グラフ があり、次数が の頂点がちょうど 個、次数が の頂点がちょうど 個ある（これで 個の頂点すべてである）。 の辺の本数を求めよ。
グラフ理論
扱うテーマ: 次数・オイラー路・ハミルトン閉路の有無、彩色数・辺彩色数、最大マッチング・最大独立集合・最小頂点被覆、最大流・最小カット、最短路・最小全域木の重み、平面グラフとオイラーの公式
難易度の目安（大学数学）
- 難易度 1 教科書の例題レベル
- 難易度 2 教科書の演習問題レベル
- 難易度 3 期末試験の応用レベル
- 難易度 4 大学院入試の標準レベル
- 難易度 5 大学院入試の難問・数学コンテストレベル
個の頂点からなる完全グラフを とする。 は、相異なる 頂点がどれもちょうど 本の辺で結ばれている単純無向グラフである。各頂点の次数と握手補題 を用いて、 の辺の本数 を求めよ（答えるのは辺の本数 だけでよい）。
正二十面体の頂点と辺を、そのまま頂点と辺とする単純無向グラフ （正二十面体グラフ）を考える。 の頂点は 個である。正二十面体の各頂点には 本の辺が集まっているので、 のどの頂点の次数も である。握手補題を用いて、 の辺の数を求めよ。
頂点集合 の重みつき有向グラフを考える。辺（始点 終点）と重みは次の 6 本である。
このグラフに負の閉路はない。ベルマン・フォード法を用いて、始点 から頂点 への最短距離 を求め、組 の形で答えよ。頂点の集合を とし、次の 5 本の重みつき有向辺をもつ有向グラフを考える（ は から への重み の辺を表す）。
始点 から頂点 への最短距離（経路上の辺の重みの和の最小値）をそれぞれ とする。ベルマン・フォード法を用いて、組 をこの順に求めよ。頂点の集合を とする有向グラフ がある。辺と重みは次の 5 本である。
ここで は から へ向かう辺の重みを表す。ベルマン・フォード法を用いて、始点 から頂点 への最短距離 を求め、組 の形で答えよ。整数 は を満たすとする。 を 個の頂点からなる完全グラフ（単純無向グラフで、相異なるどの 2 頂点も辺で結ばれているもの）とする。
が一筆書きできる、すなわち「辺をたどって進む経路で、 のすべての辺をちょうど 1 回ずつ通るもの」をもつような をすべて求めよ。ただし、この経路では同じ頂点は何度通ってもよく、始点と終点は一致してもしなくてもよい（このような経路をオイラー路という）。
整数 は を満たすとする。 頂点の完全グラフ （単純無向グラフ。たとえば は 頂点を 本の辺で結んだグラフ）が一筆書きできるような をすべて求めよ。
ここで「一筆書きできる」とは、ある頂点から出発して辺をたどり、すべての辺をちょうど 回ずつ通る経路が存在することをいう。この経路では、同じ頂点は何度通ってもよい。同じ辺を 回以上通ってはいけない。出発点と終点は一致してもしなくてもよい。
整数 は を満たすとする。 個の頂点からなる完全グラフ （相異なる 2 頂点がすべてちょうど 1 本の辺で結ばれた単純無向グラフ）を考える。
ここで、オイラー閉路とは、グラフのすべての辺をちょうど 1 回ずつ通り、出発した頂点に戻ってくる道のことである（同じ頂点は何度通ってもよい）。
がオイラー閉路をもつような をすべて求めよ。
頂点集合 と、次の 本の辺からなる辺集合 をもつ単純無向グラフ を考える。
は 2 部グラフである。 を、どの辺も両端が異なる集合に属するように 2 つの集合 （, ）に分ける。このとき、頂点 を含む方の集合を求めよ。頂点集合 と、次の 本の辺からなる辺集合 をもつ単純無向グラフ を考える。
の各頂点を白か黒の一方で塗り、どの辺についても両端の頂点が異なる色になるようにしたい。このような塗り分けができる（すなわち が 2 部グラフである）ことを確かめたうえで、頂点 と同じ色で塗られる頂点全体の集合を求めよ。頂点集合 と、次の 本の辺からなる辺集合 をもつ単純無向グラフ を考える。
の各頂点を赤・青の 色のどちらかで塗り、どの辺についても両端の頂点が異なる色になるようにする。頂点 を赤で塗るとき、赤で塗られる頂点全体の集合を求めよ。頂点集合 と、次の 本の辺からなる単純無向グラフ を考える。
の独立数 （どの 頂点も辺で結ばれていない頂点集合の大きさの最大値）と、最小頂点被覆の大きさ （すべての辺の少なくとも一方の端点を含む頂点集合の大きさの最小値）を、この順に組 で求めよ。頂点集合を とし、辺集合を
（ 本の辺）とする単純無向グラフ を考える。 の最小頂点被覆の大きさ を求めよ。ただし、頂点被覆とは、 のどの辺についても少なくとも一方の端点を含むような頂点の集合のことである。頂点集合 と、次の 本の辺からなる辺集合 をもつ単純無向グラフ を考える。
の独立数 （互いに隣接しない頂点からなる集合の最大の大きさ）と、最小頂点被覆の大きさ （すべての辺の少なくとも一方の端点を含む頂点集合の最小の大きさ）を、この順に組 で求めよ。頂点集合 をもつ重みつき単純無向グラフ があり、辺とその重みは次の 本である。
の最小全域木の重み（最小全域木に含まれる辺の重みの和）を求めよ。頂点集合を とする重みつき単純無向グラフ があり、辺とその重みは次の 本である。
の最小全域木の重み（最小全域木に含まれる辺の重みの和）を求めよ。頂点集合を とする重みつき単純無向グラフ があります。辺とその重みは、次の 本です。
の最小全域木の重み（最小全域木に含まれる辺の重みの和）を求めなさい。頂点集合 をもつ有向ネットワークがあり、有向辺とその容量は次の 本である。 始点を 、終点を とする。 を含み を含まない頂点集合 で定まる - カットの容量 を求めよ。ただし、和は , である有向辺 すべてについてとる。
頂点集合 をもつ有向ネットワークがあり、始点は 、終点は である。有向辺とその容量は次の 本である。
- カット の容量
を求めよ。頂点集合 をもつ有向ネットワークがあり、有向辺とその容量は次の 本である。
を始点、 を終点とする。頂点の集合 で定まる - カットの容量
を求めよ。ただし、和は , を満たす有向辺 すべてについてとる。次の 4 つの単純無向グラフ を考える。
- ：完全 2 部グラフ
- ：完全 2 部グラフ
- ：頂点集合 、辺集合
- ：頂点集合 、辺集合
ここで辺 は頂点 と頂点 を結ぶ辺を表す。ハミルトン閉路（すべての頂点をちょうど 1 回ずつ通って出発点に戻る閉路）をもつグラフ の番号 の集合を求めよ。
次の つの単純無向グラフ を考える。
- ：頂点集合 ，辺集合
- ：頂点集合 ，辺集合
- ：頂点集合 ，辺集合
- ：頂点集合 ，辺集合
ここで，辺 は頂点 と頂点 を結ぶ辺を表す。ハミルトン閉路（すべての頂点をちょうど 回ずつ通って出発点に戻る閉路）をもつグラフの番号 をすべて求め，集合で答えよ。
次の つの単純無向グラフ のうち、ハミルトン閉路（すべての頂点をちょうど 回ずつ通って出発点に戻る閉路）をもつものの番号をすべて求め、集合で答えよ。
- ：完全 2 部グラフ
- ：完全 2 部グラフ
- ：頂点集合 、辺集合
- ：頂点集合 、辺集合
- ：頂点集合 、辺集合
ただし、辺 は頂点 と頂点 を結ぶ辺を表す。
頂点集合 と、次の 本の辺からなる辺集合 をもつ単純無向グラフ を考える。
の独立数 （互いに隣接しない頂点からなる集合の要素の個数の最大値）を求めよ。頂点集合 と、次の 本の辺からなる辺集合 をもつ単純無向グラフ を考える。
の最大独立集合の大きさ（独立数） を求めよ。頂点集合 （ 個の頂点）と、次の 本の辺からなる辺集合 をもつ単純無向グラフ を考える。
は と を 2 つの部分とする 2 部グラフである。 の最大マッチングの大きさ を増加道を用いて求め、ケーニヒの定理を利用して、 の独立数 （最大独立集合の頂点数）を求めよ。頂点集合を とし、辺集合 を次の 本の辺からなるものとする単純無向グラフ を考える。
隣り合う（辺で結ばれた）2 頂点が異なる色になるように の頂点を塗り分けるとき、必要な色の数の最小値、すなわち彩色数 を求めよ。頂点集合 と、次の 本の辺からなる辺集合 をもつ単純無向グラフ を考える。
隣り合う（辺で結ばれた）2 頂点が異なる色になるように の頂点に色を塗るとき、必要な色の数の最小値、すなわち彩色数 を求めよ。頂点集合 と、次の 本の辺からなる辺集合 をもつ単純無向グラフ を考える。
隣り合う（辺で結ばれた）2 頂点が異なる色になるように の頂点を塗り分けるとき、必要な色の数の最小値、すなわち彩色数 を求めよ。頂点集合 をもつ有向ネットワークがあり、有向辺とその容量は次の 本である。
を入口、 を出口とする。 を満たす頂点の部分集合 を - カットといい、その容量を （ から への辺がないときは ）と定める。から への最大流の値と、容量が最小となる - カット の個数を、この順に組で求めよ。
頂点集合 をもつ有向ネットワークがあり、有向辺とその容量は次の 本である。 を始点、 を終点とする。ここで - カットとは、 かつ を満たす の部分集合 のことで、その容量を と定める。 から への最大流の値と、容量が最小となる - カット の個数を、この順に組で答えよ。
頂点集合 をもつ有向ネットワークがあり、有向辺とその容量は次の 本である。 ソースを 、シンクを とするとき、 から への最大流の値を求めよ。
は頂点が 個の連結な単純平面グラフである。 を平面上に辺が交差しないように描いたところ、すべての面（外側の非有界な面も含む）の境界がちょうど 本の辺からなる閉路（三角形）になった。この描き方における の面の数 を求めよ。
連結な単純グラフ が、辺どうしが交わらないように平面上に描かれている（平面グラフ）。 の頂点数は で、どの頂点の次数もちょうど である。この描画で平面が辺によって分けられる面の数 を求めよ。ただし、外側の有界でない領域も つの面として数える。
を頂点数 の連結な単純グラフとし、 のすべての頂点の次数は であるとする。 は平面グラフであり、辺どうしが交差しないように平面上に描かれている。この描画における面の数 を求めよ。ただし、外側の非有界な面も つの面として数える。
頂点集合を とし、辺集合 を次の 本の辺からなるものとする単純無向グラフ を考える（ は完全グラフ から辺 を除いたグラフである）。
の辺彩色数 を求めよ。ただし、辺彩色とは、共通の端点をもつ 2 本の辺が異なる色になるように各辺に色を塗ることであり、辺彩色数とはそれに必要な色の数の最小値である。頂点集合 と、次の 本の辺からなる辺集合 をもつ単純無向グラフ を考える。
同じ頂点を端点にもつ辺どうしが異なる色になるように辺を塗り分けるとき、必要な色の数の最小値（辺彩色数） を求めよ。頂点集合 と、次の 本の辺からなる辺集合 をもつ単純無向グラフ を考える。
（ は完全グラフ から辺 を 1 本だけ取り除いたグラフである。）
の辺彩色数 を求めよ。ただし、辺彩色とは、端点を共有する 2 辺が必ず異なる色になるように各辺に色を塗ることであり、 はそのような彩色に必要な色の数の最小値である。整数 は を満たすとする。完全 2 部グラフ （単純グラフ）が「オイラー閉路をもつ」または「ハミルトン閉路をもつ」の少なくとも一方を満たすような組 の個数を求めよ。
ここで、オイラー閉路とはすべての辺をちょうど 1 回ずつ通って出発点に戻る閉じた道のことであり、ハミルトン閉路とはすべての頂点をちょうど 1 回ずつ通って出発点に戻る閉路のことである。
頂点集合 をもつ有向ネットワークがあり、有向辺とその容量は次の 7 本である。
ここで、 かつ をみたす頂点の部分集合 を - カットとよび、その容量を、始点が に属し終点が に属する有向辺の容量の和と定める（ から へ向かう辺は数えない）。容量が最小となる - カット は何個あるか。
頂点集合 と、次の 10 本の辺からなる辺集合 をもつ単純無向グラフ を考える。
の独立集合（どの 2 頂点も辺で結ばれていない頂点の部分集合）の要素の個数の最大値 を求めよ。正の整数 に対し、 を、 個の頂点からなる部集合と 個の頂点からなる部集合をもつ完全二部グラフとする。
ここでは、グラフのすべての辺をちょうど 1 回ずつ通る道（始点と終点は一致してもしなくてもよい）をオイラー路とよぶ。
をみたす整数の組 のうち、 がオイラー路をもつものは何組あるか。
を正の実数とする。頂点集合 をもつ有向ネットワークがあり、有向辺とその容量は次の 8 本である。
始点を 、終点を とする - フローの最大値を とする。 が正の実数全体を動くとき、 が最大となるような の最小値を求めよ。頂点集合を とする完全グラフ を考え、相異なる 2 頂点 を結ぶ辺の重みを と の最小公倍数 と定める。この重みつきグラフの最小全域木の重み（全域木に含まれる辺の重みの和の最小値）を求めよ。
頂点集合 と、次の 本の辺からなる辺集合 をもつ単純無向グラフ を考える。
の辺をいくつかの小道（同じ辺を 度通らない歩道）に分け、すべての辺がちょうど つの小道にちょうど 回ずつ含まれるようにしたい。必要な小道の本数の最小値を求めよ。ただし、小道は辺を 本以上含むものとし、始点と終点は一致してもしなくてもよい。頂点集合 をもつ重みつき単純無向グラフ があり、辺とその重みは次の 11 本である。
ここで、たとえば は頂点 と を結ぶ重み の辺を表す。道の長さをその道に含まれる辺の重みの和で定めるとき、頂点 から頂点 への最短路の長さを求めよ。頂点集合 と、次の 本の辺からなる辺集合 をもつ単純無向グラフ （車輪グラフ）を考える。
の彩色数 （隣接する 2 頂点が異なる色になるように頂点を塗るときの色の数の最小値）と、辺彩色数 （端点を共有する 2 辺が異なる色になるように辺を塗るときの色の数の最小値）を、組 の形でこの順に求めよ。頂点集合 と、次の 本の辺からなる単純無向グラフ を考える（五角柱グラフ）。ただし添字は を法として考える（, ）。
頂点の部分集合 が の頂点被覆であるとは、 のどの辺も少なくとも一方の端点が に属することをいう。 の頂点被覆に含まれる頂点の個数の最小値を求めよ。頂点集合を とし、相異なる 2 頂点 を、一方が他方を割り切るときに限り辺で結んだ単純無向グラフを とする（たとえば は辺であり、 は辺ではない）。
のすべての辺を、どの 2 本の道も辺を共有しないような何本かの道に分ける。各辺はちょうど 1 本の道に含まれるようにする。ここで「道」とは、同じ辺を 2 度通らない歩道のことである。頂点は何度通ってもよく、始点と終点は一致してもしなくてもよい。
このように分けるとき、必要な道の本数の最小値を求めよ。
頂点集合を （ 個の頂点）とし、相異なる 2 頂点 を、 が を割り切るときに限り辺で結んだ単純無向グラフを とする。すなわち の辺は次の 本である。
の最大マッチングの辺数を 、最大独立集合の頂点数を 、最小頂点被覆の頂点数を とする。 をこの順に組 として求めよ。頂点集合を とし、相異なる 2 頂点 を、 を で割った余りが のいずれかであるときに限り辺で結んだ単純無向グラフを とする。言い換えると、 が辺で結ばれるのは または のときに限る。 の彩色数 （隣接する頂点が異なる色になるように頂点を塗るのに必要な色の最小数）と、辺彩色数 （端点を共有する辺が異なる色になるように辺を塗るのに必要な色の最小数）を、この順に組 で答えよ。
頂点集合 をもつ有向ネットワークがあり、有向辺とその容量は次のとおりである。
始点を 、終点を とするとき、 から への流れの値の最大値を求めよ。頂点集合を とし、相異なる 2 頂点 を、 が平方数（ある正の整数 を用いて と表せる数）であるときに限り辺で結んだ単純無向グラフを とする。 の独立集合（どの 2 頂点も辺で結ばれていない頂点の部分集合）の要素の個数の最大値を求めよ。
を頂点数 、辺数 の連結な単純グラフとし、 は平面に辺が交差しないように描かれている（平面グラフ）とする。この描画で平面が分けられてできる領域（外側の非有界な領域も含む）を面といい、その個数を とする。各面について、その境界をたどる閉路状の歩道の長さ（境界上の辺のうち、両側がともにその面であるものは 2 回数える）をその面の長さという。
のすべての頂点の次数が 以上であるとき、 には長さが 以下の面が少なくとも 1 つ存在することを証明せよ。
なお、連結な平面グラフに対するオイラーの公式 と、すべての面の長さの和が に等しいことは用いてよい。
を有限集合、 を有向辺の集合とし、各辺 に容量 （実数）が与えられたネットワーク を考える。相異なる 2 頂点 （始点）と （終点）を固定する。
, を満たす部分集合 を - カットといい、その容量を
と定める。容量が最小の - カットを最小カットという。, がともに最小カットであるとき、 も最小カットであることを証明せよ。
なお、フロー（各辺で を満たし、 以外の各頂点で流入量と流出量が等しい関数 ）の値 について、次の 2 つは用いてよい。
- 任意の - カット に対して
- 最大流最小カット定理（最大フローの値は最小カットの容量に等しい）を有限な連結な単純無向グラフとし、各辺 に実数の重み が与えられているとする。全域木の重みをその辺の重みの和で定め、重みが最小の全域木を最小全域木という。
の道 に対し、 に含まれる辺の重みの最大値を と書く。 を の最小全域木とし、 を の相異なる 2 頂点とする。 の中で と を結ぶ（ただ 1 つの）道を とする。このとき、 において と を結ぶ任意の道 に対して
が成り立つことを証明せよ。なお、木の基本的な性質（頂点数 の木の辺数は であること、木の 2 頂点を結ぶ道はただ 1 つであること、頂点数 で辺数 の連結グラフは木であること）は用いてよい。
を頂点数が 以上の有限な単純無向グラフとする。 の頂点彩色数（隣接する 2 頂点が異なる色になるように頂点を塗り分けるのに必要な色の最小数）を と書き、 とおく。頂点 の次数（ に隣接する頂点の個数）を と書く。
このとき、 には を満たす頂点 が少なくとも 個存在することを証明せよ。
頂点集合を とする完全グラフ を考える。相異なる 2 頂点 を結ぶ辺 には、重み
が与えられているとする（ は最小公倍数、 は最大公約数）。たとえば 、 である。この重みつきグラフの最小全域木の重み（最小全域木に含まれる辺の重みの総和）を求めよ。
を整数とする。頂点集合を とし、相異なる 2 頂点 を
のときに限り辺で結んだ単純無向グラフを とする（閉路 の 2 乗グラフ）。 の彩色数（隣接する頂点が異なる色になるように頂点を塗るのに必要な最小の色数）を 、辺彩色数（同じ頂点を端点にもつ辺が異なる色になるように辺を塗るのに必要な最小の色数）を とする。
の値を求めよ。頂点集合 をもつ有向ネットワークがあり、有向辺とその容量は次の 本である。
ここで - カットとは、、 を満たす部分集合 のことをいい、その容量を から へ向かう有向辺の容量の総和で定める。容量が最小となる - カット （最小カット）は全部でいくつあるか。頂点集合を （ 個の頂点）とし、相異なる任意の 2 頂点 を辺で結んだ完全グラフ を考える。辺 の重みを と定める。この重みつきグラフの最小全域木の重み（最小全域木に含まれる辺の重みの総和）を求めよ。
頂点集合 と、次の 本の辺からなる単純無向グラフ を考える。
で隣接していない相異なる 頂点の組 に対し、 に辺 を 本加えた単純グラフを と書く。ここで、オイラー路とはすべての辺をちょうど 回ずつ通る道（始点と終点は一致してもしなくてもよい）であり、ハミルトン閉路とはすべての頂点をちょうど 回ずつ通る閉路である。
隣接していない 頂点の組 のうち、
- がオイラー路をもつものの個数を 、
- がハミルトン閉路をもつものの個数を 、
- がオイラー路とハミルトン閉路の両方をもつものの個数をとする。組 をこの順に求めよ。
集合 の 3 元部分集合全体を頂点集合とし、2 つの頂点（3 元部分集合） を のときに限り辺で結んだ単純グラフ（クネーザーグラフ ）を とする。 の彩色数 と辺彩色数 をこの順に求めよ。
頂点集合を とし、相異なる 2 頂点 を、 のときに限り辺で結んだ単純グラフを とする（ は長さ の閉路 の補グラフである）。
の彩色数（隣り合う頂点が異なる色になるように頂点を塗るのに必要な色の数の最小値）を 、辺彩色数（端点を共有する辺が異なる色になるように辺を塗るのに必要な色の数の最小値）を とする。組 をこの順に求めよ。
0 以上の整数 に対し、 で と を 2 進法で表したときの桁ごとの排他的論理和（ビットごとの XOR）を表す。たとえば （）である。
頂点集合を とする完全グラフ において、異なる 2 頂点 を結ぶ辺の重みを と定める。このグラフの最小全域木の重み（最小全域木に含まれる辺の重みの総和）を求めよ。
各部集合がちょうど 個の頂点からなる完全 部グラフを とする。すなわち は、頂点集合 （ は互いに素で、それぞれ 個の頂点からなる）をもち、異なる部集合に属する 2 頂点はすべて辺で結ばれ、同じ部集合に属する 2 頂点は辺で結ばれない単純グラフである。
の彩色数 と辺彩色数 を求め、組 の形で答えよ。ここで辺彩色数とは、端点を共有する 2 辺が異なる色になるように全ての辺を塗るのに必要な色の数の最小値である。
頂点集合
をもつ有向ネットワーク を考える。 の有向辺とその容量は次の 本である。
- に対し、辺 。容量は順に
- すべての に対し、辺 （ 本）。容量はすべて
- に対し、辺 。容量は順ににおける から への最大流の流量を求めよ。
を、 個の頂点からなる部集合 と 個の頂点からなる部集合 をもつ完全二部グラフ（ の各頂点と の各頂点がちょうど 1 本の辺で結ばれ、それ以外に辺はない単純グラフ）とする。
を平面に描く。ただし、頂点は相異なる点、辺はその両端点を結ぶ連続曲線で表し、辺は自分の端点以外の頂点を通らず、2 本の辺は有限個の点でしか交わらず、3 本以上の辺が同じ 1 点（端点以外）で交わることはないものとする。このような描き方において、2 本の辺が端点以外で交わる点の個数を交差数とよぶ（同じ 2 本の辺が何点で交わっても、交わる点を 1 点ずつ数える）。
のすべての描き方にわたる交差数の最小値を求めよ。
頂点集合を とし、相異なる 2 頂点 を のときに限り辺で結んだ単純無向グラフを とする（ 行 列の格子グラフ）。各辺の長さを とする。
のある頂点から出発して の辺をたどり、出発した頂点に戻ってくる閉じた歩道で、 のすべての辺を少なくとも 1 回ずつ通るものを考える（同じ辺や同じ頂点を何度通ってもよい）。このような閉じた歩道の長さ（通った辺の本数を、重複も含めて数えたもの）の最小値を求めよ。
頂点集合 をもつ重みつき単純無向グラフ があり、辺とその重みは次の 本である。
全域木の重みを、その全域木に含まれる辺の重みの和と定める。辺の重みはすべて異なるので、 の最小全域木（重みが最小の全域木）はただ 1 つに定まる。これを とする。と異なる の全域木の重みの最小値を求めよ。
頂点集合 をもつ有向ネットワークがあり、有向辺 とその容量は次のとおりである。
を始点、 を終点とする。ほかの辺の容量はそのままにして、ある 1 本の辺 の容量だけを 増やしたとき、 から への最大流の値が元の値より大きくなるような番号 をすべて求め、集合で答えよ。
条件に合う問題はありません。