MO417 - Questão para a prova oral

Número: 2010-074

Enunciado: Considere o grafo G=(V,E) mostrado na figura abaixo e seja C o corte definido pela curva em vermelho. Qual das alternativas abaixo é INCORRETA?

1. C respeita exatamente oito arestas de G.
2. Existe uma única aresta leve que cruza C.
3. (h,g) é uma aresta presente em todas as árvores espalhadas mínimas de G.
4. Pelo menos duas arestas que cruzam C devem fazer parte de qualquer árvore geradora mínima de G.
5. NDA

Ideia original de: Alexandre Toshio Hirata