タイトルは要改善

連結なグラフに関する一つ構築せよ問題において、補グラフを考えると良い場合がある

頂点数3以上のグラフGが非連結である場合、任意の頂点aについて、ある非連結な頂点bがある(もしないならグラフが非連結であることと矛盾するので)

この時、aでもbでもない任意の頂点cについて、acとbcの両方の辺がGに存在することはない(もしあればcを介してaとbが連結するので)

補グラフHを考えると辺abはHに含まれ、またacかbcのいずれかはHに含まれるので、abcは連結である