完全グラフ

完全グラフ（かんぜんグラフ、英: complete graph）は、任意の 2 頂点間に枝があるグラフのことを指す。${\displaystyle n~}$ 頂点の完全グラフは、${\displaystyle K_{n}~}$で表す。また、完全グラフになる誘導部分グラフのことをクリークという^[1]。サイズ ${\displaystyle n}$ のクリークを含むグラフは「n-クリークである」と言う。辺を持つグラフは必ず 2 頂点の完全グラフを含むので 2-クリークである。また n-クリークであって、直径が n 未満となるグラフを n-クランと言う。

完全グラフ
K7, a complete graph with 7 vertices
頂点	n
辺	${\displaystyle \textstyle {\frac {n(n-1)}{2}}}$
半径	${\displaystyle \left\{{\begin{array}{ll}0&n\leq 1\\1&{\text{otherwise}}\end{array}}\right.}$
直径	${\displaystyle \left\{{\begin{array}{ll}0&n\leq 1\\1&{\text{otherwise}}\end{array}}\right.}$
内周	${\displaystyle \left\{{\begin{array}{ll}\infty &n\leq 2\\3&{\text{otherwise}}\end{array}}\right.}$
自己同型	n! (Sn)
彩色数	n
彩色指数	n if n is odd n − 1 if n is even
特性	(n − 1)-regular 対称グラフ 頂点推移的 辺推移的 強正則
表記	Kn

幾何学的、位相幾何学的性質

${\displaystyle K_{n}~}$は(n − 1)次元単体である。

例

K1: 0	K2: 1	K3: 3	K4: 6
K5: 10	K6: 15	K7: 21	K8: 28
K9: 36	K10: 45	K11: 55	K12: 66