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