Grafo completo
# Grafo completo

Nella teoria dei grafi un grafo completo è un grafo semplice nel quale ogni vertice è collegato direttamente a tutti i vertici rimanenti. I grafi completi con $n$ vertici sono tutti isomorfi. Il grafo completo astratto di $n$ vertici si denota con $\,K_{n}$. In questo grafo (in ciascuno dei grafi della classe di isomorfismo $\,K_{n}$) vi sono $\,n(n-1)/2$ spigoli: in effetti gli spigoli sono in corrispondenza biunivoca con i sottoinsiemi di due elementi dell'insieme degli $\,n$ vertici e quindi il loro numero è dato dal coefficiente binomiale ${n \choose 2}$.

Il grafo completo $\,K_{n}$ è un grafo regolare di grado $\,n-1$. Ogni grafo completo è cricca di sé stesso. I grafi completi sono i grafi massimamente connessi, in quanto l'unico taglio di vertici che li sconnette è l'insieme di tutti i suoi vertici.

Il gruppo degli automorfismi di $\,K_{n}$ è il gruppo di tutte le permutazioni dei suoi vertici, cioè in astratto il gruppo simmetrico di n oggetti.

Il teorema di Kuratowski afferma che i grafi planari sono i grafi che non contengono come minore né $\,K_{5}$ né il grafo bipartito completo $\,K_{3,3}$.

Seguono raffigurazioni che presentano con simmetria rotazionale dei grafi completi su $\,n$ vertici per $\,n=1,2,...,8$.

## Esempi

Sotto vengono mostrati i grafi completi di n vertici, con 1 ≤ n ≤ 12, insieme al rispettivo numero di lati.

| $K_{1}:0$ | $K_{2}:1$ | $K_{3}:3$ | $K_{4}:6$ |
| - | - | - | - |
| $K_{5}:10$ | $K_{6}:15$ | $K_{7}:21$ | $K_{8}:28$ |
| $K_{9}:36$ | $K_{10}:45$ | $K_{11}:55$ | $K_{12}:66$ |
