그래프 G(V, E)에 대해서 크루스칼 알고리즘을 수행하는데, G는 connected graph여야 한다.

i번째 간선(ei)까지 본 경우 만들어진 그래프를 Ti라고 하자.
그러면 크루스칼이 종료된 후 결과물은 T|E|가 된다.

임의의 한 MST를 Topt라고 하자

다음과 같은 명제를 정의하자

명제 P(i) : Ti에 i+1번째 이후의 간선 중 일부를 추가해서 MST를 만들 수 있다 (Ti를 포함하는 MST가 존재한다)


 

1. P(0)는 참이다
proof) connected이므로 spanning tree를 만들 수 있으므로 MST가 존재.


2. k < |E|인 k에 대하여, P(k)가 참일 때 P(k + 1)도 참이다
proof) P(k)가 참이라고 가정하자.

A. Tk에 ek+1를 추가하면 사이클이 생기는 경우
자명하게 P(k+1)도 참이다

B. 사이클이 생기지 않는 경우

                       i. Tk+1이 Topt의 부분집합인 경우
               자명하게 P(k+1)도 참이다

                       ii. 부분집합이 아닌 경우
             Topt에 ek+1를 추가하면 사이클이 생긴다.
             그 사이클에 있는 임의의 간선을 e’이라고 하면, cost(e’) <=cost(ek+1) 이다.

                (그렇지 않으면 ek+1가 Topt에 먼저 추가되었어야 한다)

이때, cost(e’) < cost(ek+1)이면 e’이 ek+1보다 먼저 조사되었다는 것인데,
ek+1가 추가되기 전이므로, e’을 추가해도 사이클이 생기지 않는다.
(두 간선이 모두 포함되어야 사이클이 생긴다)
그렇다면 Tk에 e’이 포함되어야 하는데 그렇지 않으므로 모순이다.

 따라서 cost(e’) = cost(ek+1)이다.
이때, Topt에서 e’ 를 빼고 ek+1를 추가하여 새로운 그래프 Topt’를 얻을 수 있다.
사이클이 생기지 않았고 비용도 같으므로 Topt’도 MST이며,
Tk+1은 Topt’의 부분집합이므로 P(k + 1)도 참이다.


3.    1, 2에 의해 P(|E|)는 참이다. T|E|에 간선을 추가하지 않고 MST를 만들 수 있다. 즉, T|E|는 MST이다.