次数2 二部グラフ 頂点数最小化

次数2の頂点を辺としてみて最大マッチング
二部グラフの最小点カバーは最大マッチングと一致する

蛇足

燃やす埋めるでの同色罰金を二部グラフの片方の変数割り当てを反転することで実現するやつと帰結先は同じ

問題例

atcoder.jp