Desenhe os grafos com as características abaixo ou justifique quando não for possível:
(i) Grafo simples de nove arestas e todos os vértices de grau 3

Passo 1

Beleza, vamos resolver esse exercício juntos! A gente precisa desenhar um grafo simples que tenha nove arestas e todos os vértices com grau 3. Vamos usar conceitos de teoria dos grafos, como o que é um grafo simples, aresta, vértice e grau. Também vamos precisar aplicar o Teorema do Aperto de Mãos para verificar se é possível ou não.

Passo 2

Primeiro, vamos lembrar o que cada termo significa:
  • Grafo simples: é um grafo que não tem laços (uma aresta que conecta um vértice a ele mesmo) nem múltiplas arestas entre os mesmos dois vértices.
  • Aresta: é a conexão entre dois vértices.
  • Vértice: é um ponto no grafo.
  • Grau de um vértice: é o número de arestas que estão conectadas a ele.

Passo 3

Agora, vamos usar o Teorema do Aperto de Mãos, que diz que a soma dos graus de todos os vértices de um grafo é igual a duas vezes o número de arestas. Matematicamente, isso é:
sumv in V grau(v) = 2 times número de arestas ú

Passo 4

No nosso caso, sabemos que temos nove arestas e que todos os vértices têm grau 3. Vamos chamar o número de vértices de $ n $.
Aplicando o Teorema do Aperto de Mãos:
n
n times 3 = 2 times 9
3n = 18
Então, precisamos de um grafo simples com 6 vértices, nove arestas e cada vértice com grau 3.

Passo 5

Agora, vamos verificar se isso é possível. Um grafo simples com 6 vértices pode ter, no máximo, 6 times 52 = 15 arestas (isso acontece no grafo completo). Como estamos pedindo por apenas 9 arestas, está dentro do limite.
Além disso, como a soma dos graus (18) é par e corresponde a duas vezes o número de arestas, não há problema em termos de viabilidade.

Passo 6

Por fim, vamos desenhar o grafo. Uma maneira de fazer isso é criar um ciclo com 6 vértices e então adicionar arestas adicionais para garantir que cada vértice tenha grau 3.
  1. Desenhe um ciclo com 6 vértices conectados em um círculo.
  2. Agora, cada vértice tem grau 2. Precisamos adicionar mais uma aresta a cada vértice.
  3. Conecte cada vértice ao vértice que está a dois passos de distância no ciclo. Isso adiciona as arestas necessárias sem criar múltiplas arestas ou laços.

Resposta

Sim, é possível desenhar um grafo simples com nove arestas onde todos os vértices têm grau 3. Um exemplo é um grafo cíclico com 6 vértices, onde além das arestas do ciclo, cada vértice está conectado ao vértice oposto, garantindo que cada um tenha grau 3.

Exercícios relacionados