>>402
二部グラフになるというのは、隣り合う頂点が同色にならないように
全ての頂点を２色に塗り分けられると言うことだよな。
まずグラフＧの極大木を考えると、木は条件を満たすように２色に塗り分けられる。
そして、補木の辺を追加するとき同色の頂点を結ぶと奇数長の閉路ができてしまう。
だから、補木の辺はすべて、異なる色の２頂点を結んだもの。
と言うことで、極大木の塗り分けがそのままグラフＧの塗り分けになる。