Seja G um grafo. Definimos o grau de x ∈ V (G) por d(x) = |{xy; xy ∈ E(G)}| Mostre que
Basta observar que cada aresta é incidente em exatamente dois vértices. Enquanto que o grau de um vértice é a quantidade de arestas que incide em um vértice. Digamos, por exemplo, que o nosso grafo seja ({x, y, z}, {x,y},{y,z}), isto é, uma árvore com 3 vértices e 2 arestas. Temos que
Ou seja, a aresta contribuiu uma unidade para o grau de x e uma unidade para grau de y. Assim como a aresta
contribuiu uma unidade para o grau de z e uma unidade para o grau de y.
Logo, somando os valores dos graus, temos 1+2+1 = 4 = 2*2 = 2* número de arestas.
A afirmação dada é conhecida como o Teorema da Soma dos Graus ou o Teorema da Mão Dupla em Teoria dos Grafos. Ela declara que a soma dos graus de todos os vértices de um grafo é igual ao dobro do número de arestas. Vamos provar isso:
Para cada aresta em um grafo, há dois "fins" que são conectados a um vértice. Portanto, se contarmos todos os "fins" de todas as arestas, obteremos exatamente o dobro do número de arestas no grafo.
Por outro lado, se somarmos os graus de todos os vértices do grafo, também estamos contando todos os "fins" de todas as arestas, pois o grau de um vértice é o número de arestas conectadas a ele.
Portanto, a soma dos graus de todos os vértices é igual ao dobro do número de arestas, o que conclui a prova. Assim, temos:
? d(v) = 2|E(G)|
para todo v ? V(G), onde d(v) é o grau do vértice v, V(G) é o conjunto de vértices do grafo G, e E(G) é o conjunto de arestas do grafo G.