各頂点に書き込む数に対する条件は以下のように言い換えられます。

1. 各 \(k\) について、各頂点の \(k\) bit 目に書き込む数は \(\mathbb Z / 2 \mathbb Z\) 上のある線形方程式を満たす必要がある。
2. \(v\) に書き込む数の \(k\) bit 目が \(1\) であるような \(k\) が、各頂点 \(v\) に対して存在する。

1 番目の条件を満たすような書き込み方全体はベクトル空間 \((\mathbb Z / 2 \mathbb Z)^N\) のある部分空間 \(W\) になっています。明らかに、第 \(v\) 成分が \(1\) となるベクトル \(r^{(v)} \in W\) が各頂点 \(v\) に対して存在する必要があります。以降はこの条件が満たされているものとして議論を進めます。

2 番目の条件を満たすために、できるだけ \(1\) を多く含むような \(W\) の元を選ぶことを考えます。ベクトル \(b \in W\) に含まれる \(1\) の個数を \(p(b)\) とすると、\(x \in W\) を一様ランダムにとったとき \(\mathbb E [p(x)] = N / 2\) です。これは任意の頂点 \(v\) について、\(W\) の元のうち第 \(v\) 成分が \(0\) のものと \(1\) のものが \(r^{(v)}\) を加算するという操作で一対一に対応することから示せます。すると、\(p(x)\) はある程度の確率で \(N / 2\) 以上になることが見込めます。実際、

\[\begin{aligned} \mathbb P \left[ p(x) \geq \frac N 2 \right] &= \mathbb P \left[ p(x) \gt \frac {N - 1} 2 \right] \\ &= \mathbb P \left[ N - p(x) \lt \frac {N + 1} 2 \right] \\ &= 1 - \mathbb P \left[ N - p(x) \geq \frac {N + 1} 2 \right] \\ &\geq 1 - \frac N {N + 1} \\ &= \frac 1 {N + 1} \end{aligned}\]

です。不等号は \(N - p(x)\) に対して Markov の不等式を用いました。 よって、\(W\) の元を一様ランダムにとることを繰り返すことで、十分高速に求めるベクトルを得ることができます。 得られたベクトルを \(1\) bit 目に書き込み、まだ \(0\) であるような頂点のうち半分以上で \(1\) であるようなベクトルを同様の手順で得ることを繰り返すと、\(6\) bit 目を書き込んだ時点で全ての頂点が非零になります \((60 \lt 2^6)\)。