Teoria dos Grafos
Enviado: 01 Dez 2019, 13:03
Questão 2: Prove que, para todo grafo simples e bipartido [tex3]G[/tex3]
com [tex3]n \ge 1[/tex3]
vértices, vale a desigualdade [tex3]\delta(G)+\Delta(G)≤n[/tex3]
. (Lembre-se de que [tex3]\delta(G)[/tex3]
e [tex3]\Delta(G)[/tex3]
denotam, respectivamente, o grau mínimo e o grau máximo de [tex3]G[/tex3]
.)
Dica: Divida sua prova em duas partes. Primeiro, prove o seguinte lema (como um passo intermediário):
Lema: Se [tex3]G[/tex3] é um grafo simples e bipartido com pelo menos três vértices, então [tex3]G[/tex3] tem algum vértice [tex3]v \in V(G)[/tex3] que satisfaz pelo menos uma das afirmações a seguir:
• [tex3]\Delta(G−v)=\Delta(G) [/tex3]
• [tex3]\delta(G−v)= \delta(G) [/tex3]
Agora, use o lema acima e prove a afirmação da Questão 2 por indução em [tex3]n[/tex3] .