グラフ理論の問題

$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$ 個存在することを証明せよ。

$G=(V,E)$ を有限な連結な単純無向グラフとし、各辺 $e\in E$ に実数の重み $w(e)$ が与えられているとする。全域木の重みをその辺の重みの和で定め、重みが最小の全域木を最小全域木という。

$G$ の道 $P$ に対し、$P$ に含まれる辺の重みの最大値を $\beta (P)$ と書く。$T$ を $G$ の最小全域木とし、$u,v$ を $G$ の相異なる 2 頂点とする。$T$ の中で $u$ と $v$ を結ぶ（ただ 1 つの）道を $P_T$ とする。このとき、$G$ において $u$ と $v$ を結ぶ任意の道 $Q$ に対して
$$\beta (P_T)\le \beta (Q)$$
が成り立つことを証明せよ。

なお、木の基本的な性質（頂点数 $n$ の木の辺数は $n-1$ であること、木の 2 頂点を結ぶ道はただ 1 つであること、頂点数 $n$ で辺数 $n-1$ の連結グラフは木であること）は用いてよい。

$G$ を頂点数 $12$ の連結な単純グラフとし、$G$ のすべての頂点の次数は $5$ であるとする。$G$ は平面グラフであり、辺どうしが交差しないように平面上に描かれている。この描画における面の数 $f$ を求めよ。ただし、外側の非有界な面も $1$ つの面として数える。

$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)$
- 最大流最小カット定理（最大フローの値は最小カットの容量に等しい）

頂点集合 $V=\{s,a_1,a_2,a_3,a_4,b_1,b_2,b_3\}$ と、次の $10$ 本の辺からなる単純無向グラフ $G$ を考える。
$$E=\{s{a}_1,a_1{a}_2,a_2{a}_3,a_3{a}_4,a_{4}s,a_1{a}_3,s{b}_1,b_1{b}_2,b_2{b}_3,b_{3}s\}$$
$G$ で隣接していない相異なる $2$ 頂点の組 $\{u,v\}$ に対し、$G$ に辺 $uv$ を $1$ 本加えた単純グラフを $G+uv$ と書く。

ここで、オイラー路とはすべての辺をちょうど $1$ 回ずつ通る道（始点と終点は一致してもしなくてもよい）であり、ハミルトン閉路とはすべての頂点をちょうど $1$ 回ずつ通る閉路である。

隣接していない $2$ 頂点の組 $\{u,v\}$ のうち、
- $G+uv$ がオイラー路をもつものの個数を $p$、
- $G+uv$ がハミルトン閉路をもつものの個数を $q$、
- $G+uv$ がオイラー路とハミルトン閉路の両方をもつものの個数を $r$

とする。組 $(p,q,r)$ をこの順に求めよ。