Para quais valores de n estes grafos têm um ciclo euleriano?
W_{n}

Passo 1

O enunciado pede para quais inteiros n o grafo roda W_{n} possui um ciclo euleriano.
O conteúdo teórico que vamos usar é o seguinte critério: um grafo conexo admite ciclo euleriano se, e somente se, todos os seus vértices têm grau par.

Passo 2

Descrevendo os graus em W_{n}:
– Os vértices do “anel” (os n-1 vértices que formam o ciclo) têm, cada um, duas arestas do ciclo mais uma aresta que vai ao centro. Logo, cada vértice do anel tem grau
\deg(\text{anel}) \;=\; 2 + 1 \;=\; 3,
que é ímpar.

Passo 3

O vértice central (o “hub”) está ligado a todos os n-1 vértices do anel, então seu grau é
\deg(\text{centro}) \;=\; n-1.
Esse valor pode ser par ou ímpar dependendo de n, mas não adianta tornar \deg(\text{centro}) par se já há vértices de grau ímpar no anel.

Passo 4

Como o grafo roda W_{n} é sempre conexo e já identificamos que os vértices do anel têm grau ímpar para todo n, falha a condição de todos os graus serem pares. Portanto não existe valor de n que torne W_{n} euleriano.

Resposta

Não há valor de n para o qual W_{n} tenha ciclo euleriano.

Exercícios de Livros Relacionados