Grafo completo
Um grafo completo é um grafo simples em que todo vértice é adjacente a todos os outros vértices. O grafo completo de n vértices é frequentemente denotado por .
Imagem: Mario Briones Iván Gutierrez · BY-SA · Openverse
O grafo K n {\displaystyle K_{n}} tem ( n 2 ) = n ( n − 1 ) 2 {\displaystyle {n \choose 2}={\frac {n(n-1)}{2}}} arestas (correspondendo a todas as possíveis escolhas de pares de vértices).
Imagem: Leandro217 · BY-SA · Openverse
O teorema de Kuratowski tem como consequência que um grafo K n {\displaystyle K_{n}} é grafo planar se e somente se n ≤ 4 {\displaystyle n\leq 4} .
Imagem: BetoBSB · BY-SA · Openverse
A quantidade de subgrafos de um grafo K n {\displaystyle K_{n}} é dada por: ∑ i = 1 n n ! i ! ( n − i ) ! ∗ 2 i ( i − 1 ) / 2 {\displaystyle \textstyle \sum _{i=1}^{n}\displaystyle {\frac {n!}{i!(n-i)!}}*2^{i(i-1)/2}}
