Mostre que em qualquer grafo o número de vértices de grau ímpar é necessariamente par.

Passo 1

Beleza, vamos lá! A questão pede para mostrar que, em qualquer grafo, o número de vértices que têm grau ímpar é necessariamente par. Estamos falando sobre Grafos e Teoria dos Grafos, especificamente sobre graus dos vértices. Para resolver isso, vamos usar o Lema da Mão dos Dedos (também conhecido como Teorema das Mãos), que relaciona a soma dos graus dos vértices com o número de arestas no grafo.

Passo 2

Primeiro, vamos lembrar o que é o grau de um vértice. O grau de um vértice é o número de arestas que estão conectadas a ele. Por exemplo, se um vértice tem 3 arestas ligadas a ele, seu grau é 3, que é ímpar.

Passo 3

Agora, vamos falar sobre a soma dos graus de todos os vértices em um grafo. O Lema da Mão dos Dedos diz que a soma de todos os graus dos vértices é igual a duas vezes o número de arestas no grafo. Em fórmula, isso fica:
sumv in V grau(v) = 2 times Número de Arestas ú
Isso significa que a soma dos graus é sempre um número par, já que é duas vezes algum número inteiro.

Passo 4

Vamos dividir os vértices em dois grupos: aqueles com grau par e aqueles com grau ímpar. Queremos provar que o número de vértices com grau ímpar é par.
Vamos chamar de o número de vértices com grau ímpar. Cada grau ímpar contribui com um número ímpar para a soma total dos graus. Se fosse ímpar, a soma dos graus seria ímpar, porque a soma de um número ímpar de números ímpares é ímpar. Mas isso contraria o que o Lema da Mão dos Dedos nos mostrou, que a soma deve ser par.

Passo 5

Como não podemos ter uma soma ímpar de graus (porque a soma deve ser par), a única possibilidade é que seja par. Portanto, o número de vértices com grau ímpar em qualquer grafo sempre será um número par.

Resposta

O número de vértices com grau ímpar em qualquer grafo é sempre par.

Exercícios relacionados