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

Número de arestas

O grafo $K_{n}$$K_{n}$ tem ${n \choose 2}={\frac {n(n-1)}{2}}$${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}$$K_{n}$ é grafo planar se e somente se $n\leq 4$$n\leq 4$.

Ver também

• Grafo bipartido completo

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