Prove que: se G ´e um grafo simples com pelo menos dois v´ertices, ent˜ao G cont´em pelo menos dois v´ertices com o mesmo grau.

Para provar que um grafo simples \( G \) com pelo menos dois vértices contém pelo menos dois vértices com o mesmo grau, vamos considerar os seguintes pontos: 1. Definições: Um grafo simples é um grafo que não possui laços (arestas que conectam um vértice a ele mesmo) e não possui arestas múltiplas (duas arestas ligando os mesmos dois vértices). O grau de um vértice é o número de arestas que incidem sobre ele. 2. Número de Vértices: Seja \( n \) o número de vértices em \( G \). Como \( G \) tem pelo menos dois vértices, temos \( n \geq 2 \). 3. Grau Máximo: O grau máximo de um vértice em um grafo simples com \( n \) vértices é \( n-1 \) (um vértice pode estar conectado a todos os outros vértices). 4. Possíveis Graus: Os graus dos vértices em \( G \) podem variar de \( 0 \) a \( n-1 \). Portanto, existem \( n \) vértices, mas apenas \( n-1 \) graus possíveis (de \( 0 \) a \( n-1 \)). 5. Caso do Grau 0: Se um vértice tem grau \( 0 \) (ou seja, não está conectado a nenhum outro vértice), então o grau máximo de todos os outros vértices deve ser pelo menos \( 1 \) (já que eles estão conectados entre si). Isso significa que pelo menos dois vértices devem ter o mesmo grau, pois os graus possíveis vão de \( 1 \) a \( n-1 \). 6. Aplicando o Princípio da Casa dos Pombos: Se considerarmos que temos \( n \) vértices e \( n-1 \) graus possíveis, pelo princípio da casa dos pombos, se \( n \) "pombos" (vértices) são colocados em \( n-1 \) "casas" (graus), pelo menos uma casa deve conter pelo menos dois pombos. Portanto, deve haver pelo menos dois vértices com o mesmo grau. Assim, concluímos que em um grafo simples \( G \) com pelo menos dois vértices, existem pelo menos dois vértices que têm o mesmo grau.