Ensino Superior ⇒ Teoria dos Grafos

[Lairão]

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].