Cada vértice pode ter como grau um número de 0 a n-1, porém o 0 e o n-1 não podem ambos ser graus de vértices, pois se um tem grau n-1 então ele está ligado a todos os outros vértices. Então há apenas n-1 possibilidades para o grau de cada vértice. Pelo pcp há dois vértices com o mesmo grau.
Em 2 de set de 2017 12:34 PM, "Daniel Rocha" <[email protected]> escreveu: > Bom dia, > > Seja G um grafo com n vértices, n maior que 1. Suponha que G não possua > loops nem mais de uma aresta unindo pares de vértices. Prove que G possui > dois vértices de graus iguais. > > Obrigado, > Daniel > -- > Esta mensagem foi verificada pelo sistema de antivírus e > acredita-se estar livre de perigo. > > > ========================================================================= > Instruções para entrar na lista, sair da lista e usar a lista em > http://www.mat.puc-rio.br/~obmlistas/obm-l.html > ========================================================================= > -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
