Isolation Lemmaとその証明

まず，$E$ の一つの要素 $e_i$ に注目する。$e_i$ 以外の重みを固定して，$e_i$ の重み $w(e_i)$ を動かしたときの様子を見る。以下の3パターンのいずれかが起こる。

• $w(e_i)$ をどのように決めても $e_i$ は全ての重み最小解に含まれない場合

• $w(e_i)$ をどのように決めても $e_i$ は全ての重み最小解に含まれる場合

• 上記のいずれにも当てはまらない場合
  このとき，あるしきい値 $p$ が存在して，
  $w(e_i) >p$ なら $e_i$ は全ての重み最小解に含まれない，
  $w(e_i) <p$ なら $e_i$ は全ての重み最小解に含まれる，
  となる。 よって，$e_i$ を含む重み最小解も $e_i$ を含まない重み最小解も存在するような $w(e_i)$ の値は高々一つである。

ここから重みの固定を外して考える。「$e_i$ を含む重み最小解も $e_i$ を含まない重み最小解も存在する」という事象を $A_i$ とおくと，上記の観察により $P(A_i)\leq \dfrac{1}{N}$ である。

よって，重み最小解が一つしかない確率は

$1-P(A_1\cup A_2\cup\cdots \cup A_n)\geq 1-\displaystyle\sum_{i=1}^nP(A_i)\geq 1-\dfrac{n}{N}$

となる。ただし，一つ目の不等号はブールの不等式（ユニオンバウンド）による。