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

Número de arestas

O grafo ${\displaystyle K_{n}}$ tem ${\displaystyle {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 ${\displaystyle K_{n}}$ é grafo planar se e somente se ${\displaystyle n\leq 4}$.

Subgrafos de um grafo completo

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

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

Ver também

• Grafo bipartido completo

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