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
(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 é:
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:
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,
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.
- Desenhe um ciclo com 6 vértices conectados em um círculo.
- Agora, cada vértice tem grau 2. Precisamos adicionar mais uma aresta a cada vértice.
- 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.