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 $K_{n}$.

Número de arestas

O grafo $K_{n}$ tem ${n \choose 2}={\frac {n(n-1)}{2}}$ arestas (correspondendo a todas as possíveis escolhas de pares de vértices).

Planaridade

O teorema de Kuratowski tem como consequência que um grafo $K_{n}$ é grafo planar se e somente se $n\leq 4$.

Subgrafos de um grafo completo

A quantidade de subgrafos de um grafo $K_{n}$ é dada por:

$\textstyle \sum _{i=1}^{n}\displaystyle {\frac {n!}{i!(n-i)!}}*2^{i(i-1)/2}$

Ver também

• Grafo bipartido completo

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