[Enunciado] Notação: O custo de uma aresta e será denotado por ce. O custo de um subgrafo não-dirigido (por exemplo, uma árvore geradora) S será denotado por c(S).
Parte 1: Se uma árvore geradora T é uma MST então ce ≥ ct para cada aresta e fora de T e qualquer aresta t do único circuito em T + e.
Prova: fácil.
Parte 2: Seja T uma árvore geradora. Se ce ≥ ct para cada aresta e fora de T e qualquer aresta t do único circuito em T + e então T é uma MST.
Prova: Escolha uma MST M que minimize a diferença M − T, ou seja, minimize o número de arestas em M que não estão em T (o que equivale a maximizar o número de arestas em M ∩ T). Provaremos que M − T é vazio.
Suponha, por contradição, que M − T não é vazio. Escolha uma aresta m de custo mínimo M − T. Seja C o único circuito em T + m. Como M não tem circuitos, C tem alguma aresta em T − M. Por hipótese,
ct ≤ cm.
Agora considere o único circuito D em M+t. Seja m' uma aresta de D em M − T. É claro que M+t−m' é uma árvore geradora. Em virtude da maneira como escolhemos m, temos cm ≤ cm' e portanto
ct ≤ cm'.
Logo, c(M+t−m') ≤ c(M). Portanto, M+t−m' é uma MST. Como t está em T − M, o conjunto (M+t−m') − T é menor que o conjunto M − T. Isso contradiz a maneira como escolhemos M. A contradição mostra que M − T é, de fato, vazio. Como M e T têm o mesmo tamanho, temos M = T. Portanto T é uma MST.