この記事ではグラフ理論の完全グラフ（Complete Graph）について解説します。

完全グラフ（Complete Graph）とは、グラフ理論における特別なグラフの一種で、次のように定義されます：

完全グラフは通常、Kₙ（Kの後に頂点数nを添えた表記）で表されます。

• K₁: 頂点が1つのグラフ（孤立点）。
• K₂: 頂点が2つあり、1本のエッジで結ばれたグラフ（線分に相当）。
• K₃: 3つの頂点が三角形状につながったグラフ。
• K₄: 4つの頂点がすべて接続されたグラフ。

1. 辺の数辺の数=2n(n−1)

   完全グラフKₙのエッジの総数は、次の式で計算されます：

   $辺の数=2n(n−1)$

   ここで、nは頂点数です。

   例：

   • K₃の辺の数

     

   • K5 の辺の数

   

2. 最大の隣接数

   各頂点は他のすべての頂点と接続されているため、隣接する頂点の数（次数）は常に n−1n-1n−1 です。

3. 対称性

   完全グラフは非常に対称的で、どの頂点から見ても同じ構造をしています。

1. 小さな完全グラフの例
2. • K₃: 三角形のようなグラフ。簡単なグラフ構造を説明するのに便利です。
   • K₄: 立方体の頂点を一面として見ることができる構造。
3. 実世界での応用例
   • 通信ネットワーク: すべてのノードが直接接続されている理想的な完全ネットワーク。
   • 組み合わせ数学: 組み合わせ問題をグラフ理論で解くときに、完全グラフが登場することが多い。
   • トラベリングセールスマン問題: 頂点が都市、辺が都市間の道を表すグラフとして完全グラフが使われる。

完全グラフは頂点数が増えると非常に密な構造になるため、平面的グラフではなくなることがあります。具体的には：

• K₅（5頂点以上）は平面上に描画できない（交差するエッジが必ず出てくる）。
• これが「平面グラフ」や「平面的グラフ」の議論で重要な役割を果たします。

隣接行列（同じ頂点同士は0、辺があれば1）を渡すだけで、定義どおりに判定できます。

def is_complete_graph(adj: list[list[int]]) -> bool:
    n = len(adj)
    for i in range(n):
        for j in range(n):
            if i != j and adj[i][j] != 1:
                return False
    return True

# K4（4頂点の完全グラフ）
k4 = [
    [0, 1, 1, 1],
    [1, 0, 1, 1],
    [1, 1, 0, 1],
    [1, 1, 1, 0],
]
print(is_complete_graph(k4))  # True

辺が1本でも欠けていれば False を返すので、「これは完全グラフか？」をそのまま自動判定できます。

平面性は「辺の数が 3n-6（nは頂点数、n≥3）を超えるか」で数値的に判定できます。K5以上が描けない理由も、この式に当てはめれば確認できます。

辺の数が上限を超えた時点で、交差なしでは描画できないと判断できます。この上限式はオイラーの多面体公式（頂点数−辺数+面数=2）から導かれる平面グラフの必要条件で、「上限以下だから必ず平面」とは限らない点に注意してください（必要条件であり十分条件ではありません）。

完全グラフは「全ての頂点が直接接続されたグラフ」であり、そのシンプルかつ密な構造が多くの数学的応用やアルゴリズムに役立ちます。特に頂点数やエッジ数の計算が容易で、グラフ理論を学ぶ際の基本概念として重要な位置を占めています。