Seja G o grafo completo em n vértices. Em outras palavras, G é o grafo simples com n 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 G e o conjunto de todas as arestas de G.
(b) Use a parte (a) para contar o número de arestas de G (em termos de n ).

Passo 1

O enunciado trata do grafo completo G com n 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 G correspondem exatamente aos subconjuntos de tamanho 2 dos n vértices (parte (a)) e então contar quantos desses subconjuntos existem (parte (b)).

Passo 2

Defina
X = lu,vsubseteq V(G)mid uneq vr
como o conjunto de todos os pares não ordenados de vértices, e seja E(G) o conjunto de arestas de G. Considere a aplicação
fcolon X to E(G), fl(u,vr)=aresta que une u e v
Como G é simples e completo, para todo u,vin X existe exatamente uma aresta (u,v), e toda aresta tem exatamente dois extremos uneq v. Logo f é bem-definida, injetora (pares distintos geram arestas distintas) e sobrejetora (toda aresta vem de algum par). Assim f é bijeção, provando a parte (a).

Passo 3

Para contar lvert E(G)rvert usamos a bijeção e calculamos
lvert Xrvert =binomn2 =n!2!(n-2)! =n(n-1)2
Como lvert E(G)rvert=lvert Xrvert, o número de arestas de G é tfracn(n-1)2.

Resposta

(a) Existe uma bijeção f entre o conjunto de pares não ordenados de vértices e o conjunto de arestas de G, pois cada aresta é determinada por dois vértices distintos e vice-versa.
(b) lvert E(G)rvert=n(n-1)2.