==== 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)$ é [[.grauV|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 é[[.defCompleto| 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$