MO405 - Exercícios - Propostos em 2002-09-25

(4.2.1) Determine k(u, v) no grafo desenhado abaixo. (Dica: use os problemas duais para dar prova curta de optimalidade)

Solução - Discutida em classe em 2002-09-30

João Paulo: k(u, v) = 3, pois basta remover três vértices {e, f, g} para quebrar todos os caminhos u-v.
Existem três caminhos disjuntos nos vértices entre u v:

u - a - e - h - k - v

u - b - f - i - l - v

u - d - g - j - h - v