[Enunciado do exercício] Seja C uma cobertura de um grafo. Queremos mostrar que
PROVA DE 1: Suponha que C é minimal. Então nenhum subconjunto próprio de C é uma cobertura. Em particular, para todo vértice v em C, o conjunto C − { v } não é uma cobertura. Em outras palavras, C − { v } não cobre alguma das arestas que têm ponta v, ou seja, v tem algum vizinho fora de C. Resumindo: todo vértice de C tem algum vizinho fora de C.
PROVA DE 2: Suponha que todo vértice de C tem um vizinho fora de C. Tome um subconjunto próprio B de C. Todo vértice em C − B tem um vizinho fora de C, e portanto fora de B. Logo, B não é uma cobertura. Conclusão: nenhum subconjunto próprio de C é uma cobertura. Portanto, C é uma cobertura minimal.