A analogia dos Apertos de Mão
Pelo Lema do Aperto de Mão descrito mais abaixo, veremos que, em um grafo, se somarmos os graus de seus vértices, esta soma é exatamente duas vezes o número de arestas. O nome deste lema se deve a uma analogia a uma observação cotidiana.
Suponhamos, por exemplo, que um matemático está em uma festa e quer ser educado com as outras pessoas, logo ele tenta socializar. Para tanto ele aperta a mão de quem quer que seja a pessoa que ele queira conversar. Até aí tudo dentro da normalidade. Mas, sendo ele um matemático que está estudando grafos, pensa: “Hum que interação interessante.” e começa a pensar o que isso pode implicar… talvez em um resultado matemático?
“No momento em que apertamos as mão”, pensa o matemático, “temos duas mãos se tocando, uma de cada pessoa envolvida. Então, se contarmos as mãos apertadas nesta festa, a soma sempre será o dobro do aperto de mãos”. Aqui o matemático chega a conclusão de que realmente há um resultado muito importante envolvendo os apertos de mãos.
Assim sendo, podemos pensar em cada mão sendo um vértice, e cada aperto de mão uma aresta. Quando somamos o grau de dois vértices de grau um, vizinhos entre si, por exemplo, temos que a soma geral é dois. Mas a quantidade de arestas é apenas uma unidade. Isso se dá pela própria dinâmica do grafo.
Com isso em mente, fica muito mais fácil e intuitivo entender o Lema do Aperto de Mão!
O lema do Aperto de Mão
Lema do Aperto de Mão
Sejam $G$ um grafo não direcionado, $V$ o conjunto de vértices e $A$ o conjunto das arestas deste grafo. Se $v ∈ V$, temos que:
\[|A| = \frac{1}{2} \sum_{v \in V} d(v)\]
onde $d(v)$ é grau de $v$ e $|A|$ é o número total de arestas de $G$.
Demonstração: Para ver isso, note que em $\sum_{v \in V} d(v)$ estamos contando cada aresta duas vezes (uma para cada extremo seu), logo o número de arestas é a metade dessa soma.
$\square$
Corolário
O número máximo de arestas em um grafo é dado por:
$$\frac{n(n-1)}{2}$$
onde $n$ é a quantidade de vértices pertencentes ao determinado grafo.
Demonstração:
O número máximo de arestas de um grafo é quando todos os seus vértices estão ligados um no outro, ou seja, ocorre quando o grafo é completo. Se um grafo completo tem $n$ vértices, cada vértice possui grau $(n - 1)$. Agora, pelo lema do aperto de mão, temos:
$$2|A| = \sum_{v\in V}d(v)=n(n-1)$$ \[\Downarrow\] $$|A| = \frac{n(n-1)}{2}$$
Segue então a prova do corolário. Com esse resultado temos que qualquer que seja a soma de arestas de um grafo qualquer, tal soma será menor ou igual ao valor determinado por esse corolário, isto é,a soma das arestas de um grafo qualquer será menor ou igual a soma de arestas de um grafo completo com o mesmo número de vértices.
$\square$