独立集合

1：$\overline G$ では、相異なる 2 頂点が隣接することと $G$ で隣接しないことが同値である（補グラフ）。
2：$I$ が独立集合であることは、両端点とも $I$ に属する辺がないこと、すなわちどの辺も $V\setminus I$ に端点をもつことと同値である。$I$ を最大独立集合とすると $V\setminus I$ は頂点被覆なので $\beta(G)\le n-\alpha(G)$ であり、$K$ を最小の頂点被覆とすると $V\setminus K$ は独立集合なので $\alpha(G)\ge n-\beta(G)$ である。
3：$v\notin I$ について、$I\cup\{v\}$ が独立集合でないことは、$v$ が $I$ のある頂点に隣接することと同値である（$I$ 自身は独立集合だから）。$\square$

四色定理 により $\chi(G)\le4$、五色定理 により $\chi(G)\le5$ であり、$n\le\chi(G)\,\alpha(G)$ から従う。$\square$

$M$ を最大マッチングとし、$M$ のどの辺の端点にもならない頂点の集合を $U$ とすると $\lvert U\rvert=n-2\lvert M\rvert$ である。孤立点がないので、$U$ の各頂点 $u$ について $u$ を端点とする辺 $e_u$ を 1 本選べる。$M$ と $\{e_u\mid u\in U\}$ を合わせた辺の集合はどの頂点も覆うので辺被覆であり、
$$ \beta'(G)\le\lvert M\rvert+\lvert U\rvert=\alpha'(G)+\bigl(n-2\alpha'(G)\bigr)=n-\alpha'(G) $$
である。
逆に、$L$ を最小の辺被覆とし、辺集合 $L$ だけからなる $V$ 上のグラフ $H$ の最大マッチング $M$ をとる。$M$ のどの辺の端点にもならない頂点の集合を $U$ とすると $\lvert U\rvert=n-2\lvert M\rvert$ である。$U$ の 2 頂点を結ぶ $L$ の辺があれば、それを $M$ に加えて $H$ のより大きいマッチングができるので、そのような辺はない。$L$ は辺被覆なので、各 $u\in U$ は $L$ のある辺 $f_u$ の端点であり、$f_u\notin M$ で、$f_u$ のもう一方の端点は $U$ に属さない。よって $u\mapsto f_u$ は $U$ から $L\setminus M$ への単射であり、$\lvert L\rvert-\lvert M\rvert\ge\lvert U\rvert=n-2\lvert M\rvert$ である。$M$ は $G$ のマッチングでもあるので
$$ \alpha'(G)+\beta'(G)\ge\lvert M\rvert+\lvert L\rvert\ge n $$
となる。2 つの不等式から等式を得る。$\square$

König の定理により $\beta(G)=\alpha'(G)$ である。prop-ind-basic の 2 から $\alpha(G)=n-\beta(G)=n-\alpha'(G)$ であり、1 が従う。孤立点がなければ thm-ind-gallai により $n-\alpha'(G)=\beta'(G)$ なので 2 が従う。$\square$

道被覆はある（1 頂点の道だけからなるもの）。$\operatorname{ter}(\mathcal P)$ が包含について極小な道被覆 $\mathcal P$（終点の集合が $\operatorname{ter}(\mathcal P)$ の真部分集合になる道被覆がないもの）について主張を示せばよい。頂点数についての帰納法で示す。頂点が 1 個なら明らかである。
$\mathcal P=\{P_1,\dots,P_m\}$ とし、$P_i$ の終点を $v_i$ とする。$\{v_1,\dots,v_m\}$ が独立なら $v_{P_i}:=v_i$ とすればよい。そうでなければ、番号を付け替えて $v_2$ から $v_1$ への辺があるとしてよい。$P_1$ が 1 頂点 $v_1$ だけなら、$P_1$ を除き $P_2$ の後ろに $v_1$ をつないだ道被覆の終点の集合は $\{v_1,v_3,\dots,v_m\}$ となり、極小性に反する。よって $P_1$ は 2 頂点以上で、$P_1$ で $v_1$ の直前の頂点を $v$ とする。$G':=G-v_1$ の道被覆 $\mathcal P':=\{P_1-v_1,P_2,\dots,P_m\}$ の終点の集合は $\{v,v_2,\dots,v_m\}$ である。
$\operatorname{ter}(\mathcal P')$ が $G'$ で極小であることを示す。$G'$ の道被覆 $\mathcal P''$ で $\operatorname{ter}(\mathcal P'')\subsetneq\operatorname{ter}(\mathcal P')$ となるものがあるとする。

• $\mathcal P''$ のある道が $v$ で終わるとき、その後ろに $v_1$ をつなぐ（$v$ から $v_1$ への辺は $P_1$ の辺）。得られる $G$ の道被覆の終点の集合は $\bigl(\operatorname{ter}(\mathcal P'')\setminus\{v\}\bigr)\cup\{v_1\}$ で、$\operatorname{ter}(\mathcal P'')\setminus\{v\}\subsetneq\{v_2,\dots,v_m\}$ なので $\operatorname{ter}(\mathcal P)$ の真部分集合になり、矛盾する。
• $v$ で終わる道がなく、ある道が $v_2$ で終わるとき、その後ろに $v_1$ をつなぐ。終点の集合は $\{v_2,\dots,v_m\}$ の $v_2$ を $v_1$ に替えたものの部分集合で、$\{v_1,v_3,\dots,v_m\}\subsetneq\operatorname{ter}(\mathcal P)$ に含まれ、矛盾する。
• どちらでもなければ $\operatorname{ter}(\mathcal P'')\subset\{v_3,\dots,v_m\}$ で、$\mathcal P''$ に 1 頂点の道 $v_1$ を加えた $G$ の道被覆の終点の集合は $\{v_1,v_3,\dots,v_m\}$ に含まれ、矛盾する。
  よって帰納法の仮定により、$\mathcal P'$ の各道から 1 頂点ずつ選んだ $G'$ の独立集合がある。$G'$ は $G$ から $v_1$ を除いたものなので、これは $G$ でも独立であり、$P_1-v_1\subset P_1$ なので $\mathcal P$ の各道から 1 頂点ずつ選んだものになっている。最後の主張は、独立集合の大きさ $\lvert\mathcal P\rvert$ が $\alpha(G)$ 以下であることによる。$\square$

1：各辺を両向きの 2 本の有向辺に置き換えた有向グラフに thm-ind-gallai-milgram を使う。有向道は $G$ の道であり、独立集合は同じである。2：トーナメントの独立集合は 1 頂点以下なので、thm-ind-gallai-milgram により 1 本の有向道で覆える。$\square$

1：最大独立集合 $I$ をとる。$\ell\in I$ ならよい。$\ell\notin I$ なら、$I$ の極大性（prop-ind-basic の 3）から $\ell$ の唯一の隣接頂点 $p$ が $I$ に属する。$I':=(I\setminus\{p\})\cup\{\ell\}$ は、$\ell$ の隣接頂点が $p$ だけなので独立集合で、$\lvert I'\rvert=\lvert I\rvert$ だから最大独立集合であり、$\ell$ を含む。
2：$F-\ell-p$ の最大独立集合に $\ell$ を加えたものは $F$ の独立集合なので $\alpha(F)\ge1+\alpha(F-\ell-p)$ である。逆に、1 の最大独立集合 $I\ni\ell$ は $p$ を含まないので、$I\setminus\{\ell\}$ は $F-\ell-p$ の独立集合であり、$\alpha(F)-1\le\alpha(F-\ell-p)$ である。
3：森の部分グラフは森であり、頂点をもつ森には孤立点か葉がある（閉路のない有限グラフで辺があれば、最長の道の端点は葉である）。孤立点 $u$ については、$u$ を含む最大独立集合があり（最大独立集合は極大なので孤立点を含む）、$\alpha(F)=1+\alpha(F-u)$ である。葉については 2 による。頂点数についての帰納法で、手順が選ぶ頂点の個数は $\alpha(F)$ に等しく、選んだ頂点は互いに隣接しない（選んだ頂点の隣接頂点はそのたびに除かれる）。$\square$