\(i\) 番目の辺が頂点 \(A_i\) と頂点 \(B_i\) を結ぶような，\(N\) 頂点 \(M\) 辺からなる無向グラフを考えます．このグラフにおいて \(i\) 番目の辺が橋であれば，どのような長さ \(M\) の \(01\) 列に対応する無向グラフにおいても，\(i\) 番目の辺は橋となります．実は，うまく \(01\) 列をとることにより，（自明な辺を除いて）その他の辺がすべて橋でないようにできます．

橋を除いて，各連結成分ごとに独立に考えることができるので，グラフは連結かつ橋を含まないとしてよいです． このとき，各辺にうまく向きを定めることで，グラフを強連結な有向グラフにすることができます．これは例えば DFS 木を考えて，木に使われている辺については親から子へ，後退辺については深い方から浅い方へ向きを付けることで可能です．

この向き付けから，次のようにして \(01\) 列を構成します．

• 頂点 \(A_i\) から頂点 \(B_i\) へ向きがついているとき，\(i\) 番目の文字は 0
• 頂点 \(B_i\) から頂点 \(A_i\) へ向きがついているとき，\(i\) 番目の文字は 1

この \(01\) 列が条件を満たすことを確かめます． 頂点数は \(2\) 以上とします． （頂点数が \(1\) の場合は橋が \(1\) つ生じます．） このとき，元のグラフに橋がないことから，橋となりうる辺は頂点 \(j\) と頂点 \((j+N)\) を結ぶ辺のみです．ここで，先程の有向グラフは強連結なので，頂点 \(j\) を含むサイクルが存在します．このサイクルに使われている辺を見れば，頂点 \(j\) と頂点 \((j+N)\) がその間の辺を除いても連結であることが分かります．よって，この \(01\) 列に対応する無向グラフには橋が存在しません．