Mostre que, em todo grafo, a soma dos graus dos vértices é igual ao dobro do número de arestas. Ou seja, todo grafo (V, A) satisfaz a identidade
sumv in V g(v)=2|A|

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 sumv in V g(v) o conjunto de vértices e sumv in V g(v) = 2|A| 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 sumv in V g(v) = 2|A| , a soma dos graus dos vértices é igual ao dobro do número de arestas, ou seja:

Exercícios relacionados