赤く塗った頂点について、次数を足し合わせることを考えます。このとき、赤く塗られた頂点どうしを結ぶ辺が \(2\) 回ずつ、異なる色の頂点を結ぶ辺が \(1\) 回ずつ数えられます。

赤く塗った頂点の次数の総和を \(S\)、赤く塗られた頂点どうしを結ぶ辺の本数を \(R\)、異なる色の頂点を結ぶ辺の本数を \(D\) とおくと

\[S = 2R + D\]

両辺を \(2\) で割った余りを考えて

\[S \equiv D \pmod{2}\]

よって、\(D\) が偶数であることは、\(S\) が偶数である、すなわち次数が奇数の頂点のうち赤く塗られているものの個数が偶数であることと同値です。

次数が奇数の頂点のうちいくつを赤く塗るかを全て調べることで、この問題を \(O(N + M)\) で解くことができます。

実装例 (C++)