グラフ理論の問題

$V$ を有限集合、$E\subseteq \{(u,v)\in V\times V\mid u\ne v\}$ を有向辺の集合とし、各辺 $e\in E$ に容量 $c(e)\ge 0$（実数）が与えられたネットワーク $N=(V,E,c)$ を考える。相異なる 2 頂点 $s$（始点）と $t$（終点）を固定する。

$s\in S$, $t\notin S$ を満たす部分集合 $S\subseteq V$ を $s$-$t$ カットといい、その容量を
$$c(S)=\sum _{(u,v)\in E,u\in S,v\notin S}c(u,v)$$
と定める。容量が最小の $s$-$t$ カットを最小カットという。

$S_1$, $S_2$ がともに最小カットであるとき、$S_1\cap S_2$ も最小カットであることを証明せよ。

なお、フロー（各辺で $0\le f(e)\le c(e)$ を満たし、$s,t$ 以外の各頂点で流入量と流出量が等しい関数 $f:E\to \mathbb{R}$）の値 $|f|$ について、次の 2 つは用いてよい。
- 任意の $s$-$t$ カット $S$ に対して $|f|=\sum _{(u,v)\in E,u\in S,v\notin S}f(u,v)-\sum _{(u,v)\in E,u\notin S,v\in S}f(u,v)$
- 最大流最小カット定理（最大フローの値は最小カットの容量に等しい）

$G$ を頂点数 $n$、辺数 $e$ の連結な単純グラフとし、$G$ は平面に辺が交差しないように描かれている（平面グラフ）とする。この描画で平面が分けられてできる領域（外側の非有界な領域も含む）を面といい、その個数を $f$ とする。各面について、その境界をたどる閉路状の歩道の長さ（境界上の辺のうち、両側がともにその面であるものは 2 回数える）をその面の長さという。

$G$ のすべての頂点の次数が $3$ 以上であるとき、$G$ には長さが $5$ 以下の面が少なくとも 1 つ存在することを証明せよ。

なお、連結な平面グラフに対するオイラーの公式 $n-e+f=2$ と、すべての面の長さの和が $2e$ に等しいことは用いてよい。

頂点集合を $V=\{1,2,3,\dots ,30\}$ とする完全グラフ $K_{30}$ を考える。相異なる 2 頂点 $i,j$ を結ぶ辺 $\{i,j\}$ には、重み
$$w(i,j)=\frac{\mathrm{lcm}(i,j)}{\gcd (i,j)}$$
が与えられているとする（$\mathrm{lcm}$ は最小公倍数、$\gcd$ は最大公約数）。たとえば $w(4,6)=\frac{12}{2}=6$、$w(3,12)=\frac{12}{3}=4$ である。

この重みつきグラフの最小全域木の重み（最小全域木に含まれる辺の重みの総和）を求めよ。

$G=(V,E)$ を頂点数が $1$ 以上の有限な単純無向グラフとする。$G$ の頂点彩色数（隣接する 2 頂点が異なる色になるように頂点を塗り分けるのに必要な色の最小数）を $\chi (G)$ と書き、$k=\chi (G)$ とおく。頂点 $v$ の次数（$v$ に隣接する頂点の個数）を $\mathrm{deg}v$ と書く。

このとき、$G$ には $\mathrm{deg}v\ge k-1$ を満たす頂点 $v$ が少なくとも $k$ 個存在することを証明せよ。

頂点集合を $V=\{1,2,3,\dots ,15\}$ とし、相異なる 2 頂点 $i,j$ を、$i+j$ が平方数（ある正の整数 $k$ を用いて $k^2$ と表せる数）であるときに限り辺で結んだ単純無向グラフを $G$ とする。$G$ の独立集合（どの 2 頂点も辺で結ばれていない頂点の部分集合）の要素の個数の最大値を求めよ。