グラフが木の場合を考えます。次数が奇数の頂点の集合を決め打ったとき、その集合のサイズが奇数なら全域部分グラフは \(0\) 通り、そうでないなら \(1\) 通りです。（証明：\(N=1\) のとき、次数が奇数の頂点が \(0\) 個のとき \(1\) 通り、\(1\) 個のとき \(0\) 通り。\(N>1\) のとき、ある葉を取ってきて、その葉に接する辺を残すかどうかをその葉の目標の次数によって決めることで 木の頂点数が \(N-1\) のケースに帰着できる。このとき、帰着前と後で次数が奇数の頂点集合のサイズの偶奇は変わらないため、偶数なら \(1\) 、奇数なら \(0\) 。）よって、答えは \(K\) が奇数なら \(0\) 、\(K\) が偶数なら \(_NC_K\) です。

グラフが連結の場合を考えます。全域木を適当に一つ取り、全域木に含まれない辺を残すかどうか自由に決めると、木のケースに帰着できます。よって、答えは \(K\) が奇数なら \(0\) 、\(K\) が偶数なら \(2^{M-N+1} \times _NC_K \) です。

グラフが非連結の場合、各連結成分でこれを求め、動的計画法や多項式の乗算などでまとめれば全体の答えが分かります。

計算量は \(O(N^2)\) や \(O(N \log^2 N)\) になります。