[Enunciado] No início de cada iteração do algoritmo de Prim vale a seguinte propriedade invariante:
sendo s a raiz
de T, ou seja,
o único vértice de T no início da
primeira iteração.
A propriedade vale trivialmente no ínicio da primeira iteração. Suponha agora que a propriedade vale no início de uma iteração qualquer que não a última. Nesse iteração, o algoritmo escolhe uma aresta e de custo mínimo na franja de T. Precisamos mostrar que, no fim dessa iteração, a propriedade invariante está satisfeita com T+e no papel de T.
Para cada aresta t de T a componente conexa de (T+e)−t que contém s é idêntica à componente conexa de T−t que contém s e portanto o custo de t é mínimo no leque dessa componente por hipótese. Resta apenas considerar o caso em que t = e, ou seja, o leque da componente conexa de (T+e)−e que contém s. Esse leque é, exatamente, a franja de T e portanto o custo de e é mínimo no leque por construção. Isso encerra a prova do invariante.
No início da última iteração, T é uma árvore geradora. Graças à invariante, T satisfaz o critério de minimalidade de MSTs. Logo, T é uma MST.