良いグラフにするために，削除する辺の本数を最小化する問題と言い換えます．

\(G = (V, E)\) における，頂点 \(i\) の次数を \(d_i\) とし，\(B_i := \max(d_i - A_i, 0)\) とします．
頂点 \(i\) では辺を \(B_i\) 本削除すれば良いので，明らかに答えは \(\sum_i B_i\) 以下です．

ここからどれだけ答えを小さくできるか考えましょう．
\(B_i\) を頂点 \(i\) で削除すべき残り本数として，辺 \((u, v)\) を削除したときに，\(B_u > 0\) かつ \(B_v > 0\) であれば，答えを \(1\) 小さくすることができます．

これを踏まえると，この問題は以下の一般グラフ最大 \(b\)-マッチング問題に帰着することができます．

一般グラフ最大 \(b\)-マッチング

グラフ \(G = (V, E)\) と，各頂点 \(i \in V\) に対し，頂点容量 \(b_i\) が与えられる．
\(E\) の部分集合 \(M\) を以下を満たすように取る．

• 各頂点 \(i \in V\) について，グラフ \((V, M)\) における頂点 \(i\) の次数は \(b_i\) 以下

\(|M|\) の最大値を求めよ．

一般グラフ最大 \(b\)-マッチングは以下のようにして \(O(N^3)\) 時間で解けることが知られています．

1. 頂点を複製して 二部最大 \(b\)-マッチング を解き，半整数解を得る．これは最大流で解ける．
2. 半整数解を Euler trail に分解し，最適解から \(O(N)\) 本少ない整数解を得る．
3. 花分解を行いながら，\(O(N)\) 回，増加路探索をする．

実装例 (C++)