\(G = (V,E)\) がよいグラフであることの必要十分条件は \(G\) が連結二部グラフであることです。

\(S \subseteq V\) について、\(f(S)\) を \(G\) をもとにした \(S\) による誘導部分グラフ \(G[S]\) からいくつかの辺を取り除いたときに \(G[S]^{\prime}\) が連結二部グラフとなるような辺の取り除き方の個数、として \(f(V)\) が求められればよいです。\(f\) を直接求めるのは難しいので、補助関数を用意して求めることを考えましょう。

\(S \subseteq V\) について、\(g(S)\) を \(G\) をもとにした \(S\) による誘導部分グラフ \(G[S]\) からいくつかの辺を取り除いたときの \(G[S]^{\prime}\) それぞれについて \(2\) 色で彩色する方法の個数を求め、その総和を取った値とします。

\(g\) は頂点を黒、白、灰に塗り分けたときに黒と白を結ぶ辺のみ存在するように辺を取り除く方法の個数を求めることで求められます。 \(f(S)\) は \(g(S)\) から \(S\) が非連結となるような彩色の個数を差し引いたのち、\(2\) で割ってやることで求められます。

\(f\) は空集合から順に埋めていくことが可能で、適切に実装すると \(O(2^N M + 3^N)\) となり、十分高速です。