Pessoal, uma pergunta sobre o exercício 3.6 das notas de aula em pdf.
Fiz a demonstração, mas tenho minhas dúvidas de que esteja correta. Vou mostrar abaixo:
Queremos provar que em um grafo G com pelo menos n>=2 vértices, existem pelo menos 2 vértices com o mesmo grau.
Seja G um grafo com n>=2 vértices.
Suponha que cada vértice do grafo possua um grau distinto dos demais. Então existirá um vértice com grau 0 e outro com grau n − 1.
Se existe um vé́rtice com grau n − 1, entã̃o esse vé́rtice é́ adjacente a todos os outros vé́rtices. Isto contradiz a suposição de um vértice com grau 0. Portanto não existe grau 0 e pelo menos dois vértices têm o mesmo grau.
Sua demonstração me parece perfeita.
A prova está correta, mas acho que você poderia esclarecer melhor a seguinte passagem:
"Suponha que cada vértice do grafo possua um grau distinto dos demais. Então existirá um vértice com grau 0 e outro com grau n − 1."
Numa primeira leitura não me pareceu evidente o porquê da segunda afirmativa. Quanto mais mastigada sua prova estiver, melhor para o leitor, mais fácil ele vai se convencer. Algo do tipo:
"Suponha que cada vértice do grafo possua um grau distinto dos demais. Então teremos vértices com graus 0, 1, ..., n-1, uma vez que um vértice não poderá ter grau maior ou igual a n."
"Suponha que cada vértice do grafo possua um grau distinto dos demais. Então existirá um vértice com grau 0 e outro com grau n − 1."
Numa primeira leitura não me pareceu evidente o porquê da segunda afirmativa. Quanto mais mastigada sua prova estiver, melhor para o leitor, mais fácil ele vai se convencer. Algo do tipo:
"Suponha que cada vértice do grafo possua um grau distinto dos demais. Então teremos vértices com graus 0, 1, ..., n-1, uma vez que um vértice não poderá ter grau maior ou igual a n."
Acho que no final você não pode dizer "Portanto não existe grau 0", pois pode existir sim; o que não existe são vértices com graus distintos 2-à-2, como você demonstrou em sua prova.