Ensino Superior ⇒ Teoria dos Grafos

[Lairão]

Questão 2: Prove que, para todo grafo simples e bipartido [tex3]G[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]G[/tex3]

com [tex3]n \ge 1[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]n \ge 1[/tex3]

vértices, vale a desigualdade [tex3]\delta(G)+\Delta(G)≤n[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\delta(G)+\Delta(G)≤n[/tex3]

. (Lembre-se de que [tex3]\delta(G)[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\delta(G)[/tex3]

e [tex3]\Delta(G)[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\Delta(G)[/tex3]

denotam, respectivamente, o grau mínimo e o grau máximo de [tex3]G[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

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

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]G[/tex3]

é um grafo simples e bipartido com pelo menos três vértices, então [tex3]G[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]G[/tex3]

tem algum vértice [tex3]v \in V(G)[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]v \in V(G)[/tex3]

que satisfaz pelo menos uma das afirmações a seguir:

• [tex3]\Delta(G−v)=\Delta(G) [/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\Delta(G−v)=\Delta(G) [/tex3]

• [tex3]\delta(G−v)= \delta(G) [/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

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

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]n[/tex3]

.