この記事は英語版の対応するページを翻訳することにより充実させることができます。（2024年5月） 翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。 英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。 翻訳後、{{翻訳告知|en|Complement graph|…}}をノートに追加することもできます。 Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針についての説明があります。

補グラフ（ほグラフ、英: complement graph）は、グラフ理論の用語。グラフ ${\displaystyle H}$ にとっての補グラフとは、${\displaystyle H}$ において隣接している頂点が補グラフでは必ず隣接していないことと同値である。したがって、あるグラフの補グラフを作成するには、そのグラフの存在しない辺を全て描き、既存の辺を全て消去すればよい。グラフの差集合とは異なり、辺だけが相補的である。

頂点群 ${\displaystyle V_{G}}$ と辺群 ${\displaystyle E_{G}}$ のグラフ ${\displaystyle G(V_{G},E_{G})}$ があるとき、その補グラフ ${\displaystyle H(V_{H},E_{H})}$ は以下のように構築される。

• ${\displaystyle V_{H}=V_{G}}$ である。
• ${\displaystyle n=|V_{G}|}$ 個の頂点のクリーク ${\displaystyle K^{n}(V_{K},E_{K})}$ について、${\displaystyle E_{H}=E_{K}\setminus E_{G}}$ とする。

補グラフは、ラムゼー理論などのグラフ理論で使われ、NP完全問題であることの証明にも使われる。

• 独立集合