Seja
o conjunto
e
o conjunto
(conjunto de todos os subconjuntos de
que têm exatamente dois elementos). Digamos que dois elemento
e
de
são adjacentes se
. Essa relação de adjacência sobre
define o grafo de Petersen. Faça uma figura do grafo. Quantos vértices e quantas arestas tem o grafo?
Passo 1
Então, a gente tem um conjunto
e quer formar todos os subconjuntos de
que têm exatamente dois elementos. Esse conjunto de subconjuntos é chamado de
e é conhecido como
. A gente vai usar isso para definir um grafo, onde cada subconjunto de dois elementos é um vértice. Dois vértices são ligados por uma aresta se os subconjuntos correspondentes não tiverem nenhum elemento em comum. Esse grafo específico é chamado de Grafo de Petersen. A gente precisa desenhar esse grafo e descobrir quantos vértices e arestas ele tem.
Passo 2
Primeiro, vamos listar todos os subconjuntos de
que têm exatamente dois elementos. Como
tem 5 elementos, o número de subconjuntos de dois elementos é dado pela combinação
.
Passo 3
Calculando
:
Então, temos 10 subconjuntos de dois elementos. Essas serão as 10 vértices do Grafo de Petersen.
Passo 4
Agora, vamos entender como as arestas são formadas. Duas vértices estão conectadas se os seus subconjuntos não tiverem elementos em comum, ou seja, se a interseção deles for vazia (
).
Passo 5
Vamos contar quantas pares de subconjuntos não compartilham nenhum elemento. Cada subconjunto de dois elementos precisa ser comparado com outros subconjuntos para verificar se não têm elementos em comum.
Passo 6
No Grafo de Petersen, cada vértice está conectado a exatamente 3 outros vértices que não compartilham elementos com ele. Como temos 10 vértices e cada um tem 3 arestas, o total de arestas seria:
Dividimos por 2 porque cada aresta é contada duas vezes nesse cálculo.
Resposta
O Grafo de Petersen tem 10 vértices e 15 arestas.