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

問題の SAT は \(N\) 変数 \(N\) 節であり，各変数がちょうど \(4\) 回登場するので，変数と節の間の二部グラフ (節が変数を含むとき辺を張る) を考えると，必ず完全マッチングが存在することが従います (Hall の定理より，あるいは正則二部グラフについての有名事実として)．このマッチングに従って各変数について対応する節を見て真偽をそれぞれ決めることによって，必ず充足できることがわかります．

完全マッチングは Hopcroft–Karp 法で \(O(N \sqrt{N})\) 時間で求まります．

完全マッチングを \(O(N)\) 時間で求めることもできます：次数がすべて \(4\) なので Euler 回路をとれますが，そこから辺を \(1\) 本おきに取り出すと次数がすべて \(2\) となります．これをもう一度行うと完全マッチングが得られます．