確率論的方法

1。 $A=\emptyset$ なら $P(A)=0$ である。後半は $P(\bigcup_iB_i)\le\sum_iP(B_i)< 1$ により、$A:=\Omega\setminus\bigcup_iB_i$ が $P(A)>0$ を満たすことによる。
2。 $\mu:=E[X]$ とし、$P(X\ge\mu)=0$ と仮定する。すると確率 1 で $\mu-X>0$ である。$0$ 以上の確率変数の期待値が $0$ なら確率 1 でその確率変数は $0$ である（Chebyshevの不等式 の定理「Markov の不等式」を $t=1/k$ に使い $k\to\infty$ とする）ので、$E[\mu-X]>0$、すなわち $\mu>\mu$ となって矛盾する。$X$ を $-X$ に替えれば後半を得る。
3。 前半は $\mathbf 1\{X\ge1\}\le X$ の期待値をとればよい。後半は、$X=0$ なら $\lvert X-E[X]\rvert\ge E[X]$ なので、Chebyshevの不等式 の定理「Chebyshev の不等式」による。$\square$

各点の色を独立に確率 $\frac12$ ずつで決める（$2^{\lvert V\rvert}$ 通りの塗り方が等確率の有限確率空間）。辺 $e$ が単色になる事象 $B_e$ の確率は、$e$ の $k$ 点がすべて赤かすべて青なので $2\cdot2^{-k}=2^{1-k}$ である。$\sum_eP(B_e)=\lvert\mathcal E\rvert2^{1-k}< 1$ なので、prop-pm-principle の 1 により、どの辺も単色でない塗り方がある。$\square$

$\theta:=\frac1{2g}$ とし、$n$ を大きくとって $p:=n^{\theta-1}$、ランダムグラフ $G\sim G(n,p)$ を考える。
段 1（短い閉路は少ない）。 長さ $i$ の閉路は、異なる $i$ 個の頂点の並び $(v_1,\dots,v_i)$ を、巡回と向きの反転で同一視したもの（$2i$ 個の並びが同じ閉路を表す）なので、$K_n$ の中に $n(n-1)\cdots(n-i+1)/(2i)\le n^i/(2i)$ 個ある。それぞれが $G$ に含まれる確率は $p^i$ である。長さ $g$ 以下の閉路の個数を $Y$ とすると、期待値の線形性により
$$ E[Y]\le\sum_{i=3}^g\frac{(np)^i}{2i}\le\sum_{i=3}^gn^{\theta i}\le g\,n^{\theta g}=g\sqrt n $$
である（$np=n^\theta\ge1$）。Chebyshevの不等式 の定理「Markov の不等式」により $P(Y\ge n/2)\le2E[Y]/n\le2g/\sqrt n$ である。
段 2（大きな独立集合はない）。 $a:=\lceil3\ln n/p\rceil$ とする。$a\le n$ のとき、ある $a$ 元集合が独立集合になる確率は $(1-p)^{\binom a2}\le e^{-pa(a-1)/2}$ なので
$$ P(\alpha(G)\ge a)\le\binom na(1-p)^{\binom a2}\le\bigl(ne^{-p(a-1)/2}\bigr)^a $$
である。$p(a-1)\ge3\ln n-p\ge3\ln n-1$ なので $ne^{-p(a-1)/2}\le e^{1/2}n^{-1/2}$ であり、$n\ge3$ でこれは $1$ 未満なので、右辺は $e^{1/2}n^{-1/2}$ 以下である。$a>n$ なら左辺は $0$ である。
段 3（悪い部分を取り除く）。 段 1・2 の上界の和は $n\to\infty$ で $0$ に近づくので、$n$ が十分大きければ $P(Y\ge n/2)+P(\alpha(G)\ge a)< 1$ であり、prop-pm-principle の 1 により、$Y< n/2$ かつ $\alpha(G)< a$ となるグラフ $G$ がある。$G$ の長さ $g$ 以下の閉路のそれぞれから頂点を 1 つずつ選んで取り除いたグラフを $H$ とする。$H$ の頂点は $n/2$ 個より多い。$H$ の閉路は $G$ の閉路であり、長さ $g$ 以下の閉路はすべて頂点を失っているので、$H$ の内周は $g$ より大きい。$H$ の独立集合は $G$ の独立集合なので $\alpha(H)\le\alpha(G)< a$ である。彩色数 の命題「彩色数の基本評価」により
$$ \chi(H)\ge\frac{\lvert V(H)\rvert}{\alpha(H)}>\frac{n/2}a\ge\frac{n}{2(3n^{1-\theta}\ln n+1)} $$
である（$a\le3\ln n/p+1$）。右辺は $n^\theta/\ln n$ の程度で $\infty$ に発散するので、$n$ を十分大きくとれば $k$ より大きい。$\square$

主張。 $S\subset\{1,\dots,m\}$、$i\notin S$ で、$P(\bigcap_{j\in S}\overline{A_j})>0$ なら
$$ P\Bigl(A_i\Bigm|\bigcap_{j\in S}\overline{A_j}\Bigr)\le x_i $$
である（$S=\emptyset$ のとき共通部分は $\Omega$）。
$\lvert S\rvert$ についての帰納法で示す。$S_1:=S\cap\Gamma(i)$、$S_2:=S\setminus S_1$ とおき、$C_T:=\bigcap_{j\in T}\overline{A_j}$ と書く。$S_2$ は $\Gamma(i)\cup\{i\}$ と交わらないので、依存グラフの条件により $P(A_i\cap C_{S_2})=P(A_i)P(C_{S_2})$ である。$C_S\subset C_{S_2}$ なので $P(C_{S_2})>0$ である。
$S_1=\emptyset$ なら $S=S_2$ で、$P(A_i\mid C_S)=P(A_i)\le x_i$ である（$x_i$ に掛かる積は $1$ 以下）。$S_1=\{j_1,\dots,j_r\}$（$r\ge1$）とする。$C_S=C_{S_1}\cap C_{S_2}$ なので
$$ P(A_i\mid C_S)=\frac{P(A_i\cap C_{S_1}\cap C_{S_2})}{P(C_S)}=\frac{P(A_i\cap C_{S_1}\mid C_{S_2})}{P(C_{S_1}\mid C_{S_2})} $$
である。分子は $P(A_i\mid C_{S_2})=P(A_i)\le x_i\prod_{j\in\Gamma(i)}(1-x_j)$ 以下である。分母は
$$ P(C_{S_1}\mid C_{S_2})=\prod_{l=1}^r\Bigl(1-P\bigl(A_{j_l}\bigm|C_{S_2\cup\{j_1,\dots,j_{l-1}\}}\bigr)\Bigr) $$
と書ける（条件の事象はどれも $C_S$ を含むので確率は正）。$S_2\cup\{j_1,\dots,j_{l-1}\}$ は $j_l$ を含まず、要素の個数は $\lvert S\rvert$ より小さいので、帰納法の仮定により各因子は $1-x_{j_l}$ 以上である。$\{j_1,\dots,j_r\}\subset\Gamma(i)$ で $0< 1-x_j\le1$ なので、分母は $\prod_{j\in\Gamma(i)}(1-x_j)$ 以上である。よって $P(A_i\mid C_S)\le x_i$ である。
結論。 $i=1,\dots,m$ について順に、$P(C_{\{1,\dots,i\}})=P(C_{\{1,\dots,i-1\}})\bigl(1-P(A_i\mid C_{\{1,\dots,i-1\}})\bigr)\ge P(C_{\{1,\dots,i-1\}})(1-x_i)$ である（$P(C_{\{1,\dots,i-1\}})>0$ は帰納的にわかるので条件付き確率が定まり、主張が使える）。掛け合わせて結論を得る。$\square$

$d=0$ なら $\Gamma(i)$ はどれも空なので、$x_i:=P(A_i)\le p\le\frac1e< 1$ とおけば thm-pm-lll の仮定が成り立つ。以下 $d\ge1$ とし、すべての $i$ で $x_i:=\frac1{d+1}$ とおく。$(1+\frac1d)^d\le e$ なので $(1-\frac1{d+1})^d=(1+\frac1d)^{-d}\ge\frac1e$ であり、
$$ x_i\prod_{j\in\Gamma(i)}(1-x_j)\ge\frac1{d+1}\Bigl(1-\frac1{d+1}\Bigr)^d\ge\frac1{e(d+1)}\ge p\ge P(A_i) $$
である。$x_i< 1$ なので thm-pm-lll が使える。$\square$

prop-pm-hypergraph-first の証明と同じく各点の色を独立に確率 $\frac12$ ずつで決め、辺 $f$ が単色になる事象を $A_f$ とする。$P(A_f)=2^{1-k}$ である。辺を頂点とし、交わる 2 辺を結んだグラフ $D$ が依存グラフであることを示す。$A_f$ は $f$ の点の色だけで決まり、$f$ と交わらない辺 $f'$ の事象 $A_{f'}$ は $f$ の外の点の色だけで決まる。各点の色は独立なので、$f$ の点の色の組と $f$ の外の点の色の組は独立であり、$A_f$ はそれらの $A_{f'}$ の補事象の任意の共通部分と独立である。$D$ の次数は $d$ 以下で、$e\cdot2^{1-k}(d+1)\le1$ なので、cor-pm-lll-symmetric により、どの辺も単色でない塗り方が正の確率で、したがって少なくとも 1 つ存在する。$\square$

要点：三角形の個数 $X$ の平均は $\binom n3p^3$ で、分散は辺を共有する三角形の対からしか生じない。