Mostre que, em todo grafo, a soma dos graus dos vértices é igual ao dobro do número de arestas. Ou seja, todo grafo
satisfaz a identidade
Passo 1
Vamos dar uma olhada no que o exercício está pedindo. A questão quer que a gente mostre que, em qualquer grafo, a soma dos graus dos vértices é igual ao dobro do número de arestas. Isso envolve entender conceitos básicos de teoria dos grafos, como o que são vértices, arestas e graus dos vértices.
Passo 2
Primeiro, vamos entender o que é o grau de um vértice. O grau de um vértice é simplesmente o número de arestas que estão conectadas a ele. Por exemplo, se um vértice tem 3 arestas ligadas a ele, dizemos que seu grau é 3.
Passo 3
Agora, vamos analisar o que significa a soma dos graus de todos os vértices em um grafo. Se você somar o grau de cada vértice, está contando todas as conexões feitas por todas as arestas no grafo. Mas atenção: cada aresta conecta dois vértices, então cada aresta está sendo contada duas vezes nessa soma.
Passo 4
Vamos ilustrar isso com uma fórmula. Seja
o conjunto de vértices e
o conjunto de arestas do grafo. A soma dos graus dos vértices é:
Como cada aresta conecta dois vértices, cada aresta contribui com 2 para essa soma. Portanto, se temos
arestas, a soma total dos graus será:
Resposta
Assim, mostramos que em todo grafo
, a soma dos graus dos vértices é igual ao dobro do número de arestas, ou seja: