支配集合

1：$D\subset D'$ なら $N[D]\subset N[D']$ である。
2：$\lvert N[v]\rvert\le\Delta(G)+1$ なので、支配集合 $D$ について $n=\lvert N[D]\rvert\le\lvert D\rvert(\Delta(G)+1)$ である。
3：独立集合 の命題「独立集合の基本性質」の 3 による（$v\notin I$ について、$I\cup\{v\}$ が独立集合でないことと、$v$ が $I$ のある頂点に隣接することが同値）。空集合から始めて頂点を加えていけば極大な独立集合ができるので、独立支配集合は存在する。最大独立集合は極大なので、それ自身が独立支配集合であり、$i(G)\le\alpha(G)$ である。$\gamma(G)\le i(G)$ は定義から明らかである。
4：頂点被覆 $K$ と $v\notin K$ をとる。$v$ は孤立点でないので辺 $vu$ があり、$K$ はこの辺の端点を含むが $v\notin K$ なので $u\in K$ である。よって $v$ は $K$ の頂点に隣接する。
5：$D$ が $G$ の支配集合なら、$D\cap V(G_j)$ は $G_j$ の支配集合である（$G_j$ の頂点に隣接する頂点は $G_j$ に属する）。逆に各 $G_j$ の支配集合の和集合は $G$ の支配集合である。$\square$

最小の支配集合 $D$ をとる。$\ell$ を支配するには $N[\ell]=\{\ell,p\}$ の頂点が要るので、$D$ は $\ell$ か $p$ を含む。$\ell\in D$ なら $D':=(D\setminus\{\ell\})\cup\{p\}$ とおく。$N[\ell]=\{\ell,p\}\subset N[p]$ なので $N[D']\supset N[D]=V$ であり、$D'$ は支配集合で $\lvert D'\rvert\le\lvert D\rvert$ である。よって $D'$ も最小で、$p\in D'$ である。$p\in D$ のときは、$\ell\in D$ なら $D\setminus\{\ell\}$ も支配集合になり最小性に反するので、$\ell\notin D$ である。$\square$

$D$ が支配集合であることから、$D$ が極小であることは、どの $v\in D$ についても $D\setminus\{v\}$ が支配集合でないことと同値である（1 により、真部分集合が支配集合なら、それを含む $D\setminus\{v\}$ の形の集合も支配集合）。$D\setminus\{v\}$ が支配集合でないことは、$D\setminus\{v\}$ に属さず、$D\setminus\{v\}$ のどの頂点にも隣接しない頂点 $x$ があることである。$x=v$ の場合が (a) であり、$x\ne v$ の場合は、$x\notin D$ で $x$ は $D$ のある頂点に隣接するので、それは $v$ だけ、すなわち (b) である。$\square$

$V\setminus D$ の頂点は $V\setminus D$ に属するので、$D$ の各頂点 $v$ が $V\setminus D$ の頂点に隣接することを示せばよい。prop-dom-minimal により、$v$ は (a) か (b) を満たす。(b) なら、$v$ は $u\notin D$ に隣接する。(a) なら、$v$ の隣接頂点はどれも $D$ に属さず、$v$ は孤立点でないので隣接頂点があり、それは $V\setminus D$ に属する。
後半：極小な支配集合 $D$ をとる（最小の支配集合は極小なので、それをとればよい）。$D$ と $V\setminus D$ はどちらも支配集合なので、$\gamma(G)\le\min(\lvert D\rvert,n-\lvert D\rvert)\le n/2$ である。$\square$

$p:=\log(\delta+1)/(\delta+1)$ とおく。$x>0$ で $\log x\le x-1< x$ なので $0\le p< 1$ である。各頂点を、互いに独立に確率 $p$ で選んで得られる無作為な部分集合を $X$ とする（$V$ の部分集合 $S$ に確率 $p^{\lvert S\rvert}(1-p)^{n-\lvert S\rvert}$ を与える有限の確率空間）。$Y:=V\setminus N[X]$ を、$X$ に支配されない頂点の集合とすると、$X\cup Y$ はつねに支配集合である。
期待値の線形性により $E\lvert X\rvert=np$ である。頂点 $v$ が $Y$ に属するのは、$N[v]$ のどの頂点も選ばれないときなので、$\lvert N[v]\rvert\ge\delta+1$ と $1-p\le e^{-p}$ から
$$ P(v\in Y)=(1-p)^{\lvert N[v]\rvert}\le(1-p)^{\delta+1}\le e^{-p(\delta+1)}=\frac{1}{\delta+1} $$
である。よって
$$ E\lvert X\cup Y\rvert\le E\lvert X\rvert+E\lvert Y\rvert\le np+\frac{n}{\delta+1}=\frac{n\bigl(1+\log(\delta+1)\bigr)}{\delta+1} $$
となる。確率変数 $\lvert X\cup Y\rvert$ は、少なくとも 1 つの $S$ で期待値以下の値をとるので、その大きさの支配集合 $X\cup Y$ がある。$\square$

$\gamma(G')\le\beta(G)$：$G$ の頂点被覆 $K$ をとる。元の頂点 $v\notin K$ は、prop-dom-basic の 4 の証明のとおり $G$ の辺で $K$ の頂点に隣接する。新しい頂点 $x_e$（$e=uv$）は、$u,v$ の一方が $K$ に属するのでそれに隣接する。よって $K$ は $G'$ の支配集合である。
$\gamma(G')\ge\beta(G)$：$G'$ の支配集合 $D$ をとり、$D$ の新しい頂点 $x_e$（$e=uv$）をそれぞれ $u$ に置き換えた集合を $D'$ とする。$\lvert D'\rvert\le\lvert D\rvert$ である。$D'$ も $G'$ の支配集合である。実際、$x_e$ が支配していたのは $x_e,u,v$ だけで、$u$ はこの 3 つすべてに隣接するか一致する（$uv$ は $G$ の辺）。$D'$ は元の頂点だけからなり、各 $x_e$（$e=uv$）を支配するので $u$ か $v$ を含む。よって $D'$ は $G$ の頂点被覆で、$\beta(G)\le\lvert D'\rvert\le\lvert D\rvert$ である。$\square$