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}$.

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).

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

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}$

• 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}$