MO417 - Questão para a prova oral

Número: 074

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

1. C respeita exatamente 8 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 uma mesma árvore geradora mínima de G.
5. NDA

Autor(a): Alexandre Toshio Hirata