(より詳しい解説は後日ブログで公開します)

頂点は金色，辺は銀色の方が条件を満たしやすいので，色を言い換えて

• 任意の赤色の辺に対し，それが結ぶ頂点のうち少なくとも 1 つは緑色である．
• 任意の赤色の頂点に対し，それに接続する辺のうち少なくとも 1 つは緑色である．

として考えることにします．

これら \(N+M\) 個の条件について包除原理を適用すると，\(-1 \equiv 1 \pmod{2}\) なので係数は無視できて，頂点と辺を緑色・赤色・青色に塗って以下を満たす方法の個数を数えればよいです：

• 任意の青色の辺に対し，それが結ぶ頂点はいずれも緑色でない．
• 任意の青色の頂点に対し，それに接続する辺はいずれも緑色でない．

この条件は緑色と青色について対称なので，\({} \bmod 2\) でほとんどがキャンセルし，残るのはすべてが赤色の場合のみです．よって答えは常に奇数となります．

なお，無向グラフの支配集合の個数は常に奇数であり，この問題や上の証明はその特殊ケースです．