Seja
o grafo completo em
vértices. Em outras palavras,
é o grafo simples com
vértices no qual todo vértice compartilha uma aresta com todos os outros vértices.
(a) Explique por que existe uma bijeção entre o conjunto de todos os pares (não ordenados) de vértices em
e o conjunto de todas as arestas de
.
(b) Use a parte (a) para contar o número de arestas de
(em termos de
).
(a) Explique por que existe uma bijeção entre o conjunto de todos os pares (não ordenados) de vértices em
(b) Use a parte (a) para contar o número de arestas de
Passo 1
O enunciado trata do grafo completo
com
vértices, em que cada par de vértices está ligado por exatamente uma aresta. O conteúdo é combinatória básica: precisamos mostrar que as arestas de
correspondem exatamente aos subconjuntos de tamanho 2 dos
vértices (parte (a)) e então contar quantos desses subconjuntos existem (parte (b)).
Passo 2
Defina
como o conjunto de todos os pares não ordenados de vértices, e seja
o conjunto de arestas de
. Considere a aplicação
Como
é simples e completo, para todo
existe exatamente uma aresta
, e toda aresta tem exatamente dois extremos
. Logo
é bem-definida, injetora (pares distintos geram arestas distintas) e sobrejetora (toda aresta vem de algum par). Assim
é bijeção, provando a parte (a).
Passo 3
Para contar
usamos a bijeção e calculamos
Como
, o número de arestas de
é
.
Resposta
(a) Existe uma bijeção
entre o conjunto de pares não ordenados de vértices e o conjunto de arestas de
, pois cada aresta é determinada por dois vértices distintos e vice-versa.
(b) .
(b)