タイトルは要改善 連結なグラフに関する一つ構築せよ問題において、補グラフを考えると良い場合がある 非連結なグラフの補グラフは連結 頂点数3以上のグラフGが非連結である場合、任意の頂点aについて、ある非連結な頂点bがある(もしないならグラフが非連結であることと矛盾するので) この時、aでもbでもない任意の頂点cについて、acとbcの両方の辺がGに存在することはない(もしあればcを介してaとbが連結するので) 補グラフHを考えると辺abはHに含まれ、またacかbcのいずれかはHに含まれるので、abcは連結である