Pessoal, estou refazendo todos os exercícios do material da sala de aula e fiquei com dúvida neste aqui (por enquanto, mais dúvidas vão surgir)
Será que alguém pode validar meu raciocínio por favor? Eu sei que a resposta está certa, eu só não sei como responder formalmente:
P: Se um grafo tem mais de um vértice, é verdade que tem dois vértices distintos v e w tais que
|N(v)| = |N(w)|?
R: Sim. É fácil verificar isso algoritmamente para um grafo dado G:
Comece com o conjunto de vértices, sem nenhuma aresta. Acrescente uma aresta de cada vez.
A primeira aresta acrescentada deixa dois vértices com o mesmo grau (antes todos tinham grau 0, agora dois tem grau 1)
na próxima inserção, ou um vértice fica com grau 2 e dois com grau 1, ou então teremos 4 vértices com grau 1... ao acrescentar um por vez, aumentando em 1 o grau de dois vértices fica claro que sempre existirão dois vértices com o mesmo grau...
agora... como explicar isso formalmente?
> ao acrescentar um por vez, aumentando em 1
> o grau de dois vértices fica claro
Não fica claro não.
Uma prova que envolve "construir o grafo"
não faz muito sentido.
Você deve imaginar que alguém te deu um grafo
e que você deve provar que AQUELE grafo tem
dois vértices de mesmo grau.
Hun... vou tentar resolver e ver com o gabriel na segunda se eu acertei! Valeu professor!