크러스컬 알고리즘
정확성 증명

P를 연결 가중 그래프라 하고,  Y를 크러스컬 알고리즘을 사용하여 생성된  P의 부분 그래프라고 가정하자.  Y는 순환을 가질 수 없다. 마지막 변이 하나 추가되어 순환을 생성한 것이라면, 그 마지막 변은 서로 다른 나무 사이에 존재할 수 없으며, 한 부분나무 속에 존재해야만 하기 때문이다. (순환을 만들려면 각 꼭짓점들이 한 부분나무 속에서 이미 이어져 있어야 한다. 알고리즘의 절차상 그러한 마지막 변을 만들 수 없다는 뜻이다.)  Y는 비연결 그래프일 수 없다.  Y 내에 또다른 연결 성분이 있었다면, 알고리즘의 절차에 의해, 그 둘을 연결하는 변이 추가되었을 것이기 때문이다. 결론을 내리면,  Y는  P의 신장 부분 그래프이다.
다음으로는 신장 부분 그래프  Y가 최소 신장 부분 그래프(minimum spanning tree)임을 보이겠다.
Y_{1}이  최소 신장 부분 그래프라고 가정하자. 만약  Y=Y_{1}이면  Y도  최소 신장 부분 그래프가 된다. 이게 사실이 아니라고 가정하자.  e가  Y에는 있으나  Y_{1}에는 없는 변이라고 가정하자.  Y_{1}\cup {e}는 순환을 가질 수밖에 없다. 신장 부분 그래프에 변을 하나 더하면 더 이상 신장 부분 그래프가 아니기 때문이다. 이 순환은 다른 하나의 변 f를 가지는데,  f는  e가  Y에 추가되는 알고리즘의 단계에서 고려 안 된 변일 수밖에 없다. 안 그랬다면  e는 같은 나무의 다른 가지(branch)들을 서로 연결했을 것이고, 서로 다른 나무들은 연결시키지 않았을 것이기 때문이다. 그러므로 Y_{2}=Y_{1}\cup {e}\setminus {f}도 역시 신장 부분 그래프이다. 이 신장 부분 그래프의 총 가중치 합(total weight)은  Y_{1}의 총 가중치보다 작다. 그 까닭은  w(e)\leq w(f)이므로 알고리즘이  f를 방문하기 전에  e를 먼저 방문했기 때문일 것이다. 만약 가중치들이 같았다면, 우리는  Y에는 있으나  Y_{1}에는 없는 변  e를 생각할 수 있다. 만약 남아 있는 변이 없었다면,  Y나  Y_{1}가 서로 다른 변들로 구성되어 있었더라도  Y의 총 가중치 합이  Y_{1}의 총 가중치 합과 같을 것이다. 이 때도 역시  Y는 최소 신장 부분 그래프가 된다. 만약  Y_{2}의 총 가중치 합이  Y_{1}의 총 가중치 합보다 작은 경우에는,  Y_{1}이 최소 신장 부분 그래프가 아니라는 결론에 다다르게 된다. 이것은  w(e)<w(f)인 변  e,f가 있다는 처음의 가정에 위배되게 된다. 결론적으로,  Y는 ( Y_{1}과 변들도 같고, 가중치도 같은) 완전한 최소 신장 부분 그래프가 될 수밖에 없다.
크러스컬 알고리즘의 결과인 신장 부분 그래프 Y의 비용이 최소임을 보이는 다른 방법은 수학적 귀납법이다. 다음 명제가 참임을 수학적 귀납법으로 증명한다.
"만약 F가 크러스컬 알고리즘의 각 단계에서 나타나는 변의 집합 중의 하나라고 하면 F를 포함하는 최소 생성나무가 있다."
이 명제를 증명하면 결국 크러스컬 알고리즘의 마지막 단계에 나타나는 생성나무 Y를 포함하는 최소 생성나무가 있고 Y가 곧 최소 생성나무이다.
알고리즘의 첫 단계, 즉, 변을 선택하지 않은 단계에서 F는 공집합이다. 이때, 크러스컬 알고리즘을 적용하는 그래프는 유한개의 점과 변을 가진다. 그러므로 생성나무를 유한개 가진다. 정확성 증명의 처음에 크러스컬 알고리즘의 결과로 Y가 생성나무임을 증명했으므로 그래프가 가지는 생성나무는 하나 이상의 유한개이다. 그러므로 최소 생성나무가 존재한다. 그러므로 공집합 F를 포함하는 최소 생성나무가 존재한다.
크러스컬 알고리즘의 각 단계 중에 나타나는 변의 집합 F를 포함하는 최소 생성나무 T가 있다고 가정하자.
알고리즘의 다음 단계에 추가하는 변을 e라 하면 다음 단계의 집합은 F에 e를 추가한 집합  F\cup {e}이다.  F\cup {e}를 포함하는 최소 생성나무가 존재함을 보인다. e는 T의 변이거나 아니다. (1) e가 T의 한 변이면  F\cup {e}를 포함하는 최소 생성나무는 T이다. (2) e가 T의 변이 아니라고 하자. 그런데 T는 그래프의 모든 점을 가지는 생성나무이다. 그러므로 e는 T가 가진 두 점 A와 B를 양끝 점으로 한다. T는 나무이므로 A에서 B로의 경로 p가 있다. 그리고 p는 유일하다. 그러므로 T에 e를 추가하면  T\cup {e} 안에 회로 C가 생긴다. 이때  T\cup {e}에서 회로는 C하나뿐이다.  F\cup {e}는 크러스컬 알고리즘의 정의 때문에 회로를 가질 수 없다. 그러므로 회로 C를 가질 수 없다. 그러므로 F도 "회로 C에서 변 e가 모자란 경로 p 전체"를 가질 수 없다. 그러므로 F가 가지지 않은 "경로 p의 변 f"가 있다. f가 경로 p에 있으므로 회로 C에도 있다. 그런데 회로 C가  T\cup {e}에서 유일한 회로이므로 f를  T\cup {e}에서 빼면 다시 나무가 된다.  T\cup {e}-f는 그래프상의 점은 모두 가지므로 생성나무가 된다. 이제  T\cup {e}-f의 비용이 최소생성나무 T의 비용 이하임을 보인다. 크러스컬 알고리즘은 매 단계에서 최소 가중치의 변을 추가한다. F는 e와 f를 가지지 않고  f의 가중치가 e 이상이기 때문에 F를 만든 단계 다음에 e를 추가한 것이다. 그러므로  T\cup {e}-f의 비용은 T의 비용 이하이다. 즉,  T\cup {e}-f는 최소 생성나무이다.  T\cup {e}는  F\cup {e}를 포함하지만 f는 F의 원소가 아니므로  T\cup {e}-f는  F\cup {e}를 포함한다. 그러므로  F\cup {e}를 포함하는 최소 생성나무  T\cup {e}-f가 존재한다.
크러스컬 알고리즘 다른 형태의 증명
나무에 관한 정리에서 n개의 꼭짓점을 가진 그래프가 연결 그래프일 때, 회로를 가지지 않는 것과 n-1개의 변을 가지는 것은 동일함이 알려져 있다. 알고리즘의 각 단계에서 얻는 그래프는 연결을 항상 유지하고 있으며 마지막 단계의 그래프는 n-1개의 변이 남으므로 회로를 가지지 않는다. 그러므로 알고리즘을 통해 얻은 그래프는 생성나무이다.
이제 남은 것은 결과로 얻은 생성나무가 최소 비용임을 보이는 것이다. 그러므로 다음과 같은 명제를 수학적 강귀납법으로 증명한다.
"알고리즘의 각 단계의 그래프는 최소비용 생성나무를 포함한다."
알고리즘의 최초 단계의 그래프는 변을 제거하지 않았으므로 최소비용 생성나무를 당연히 포함한다.
알고리즘의 처음부터 n개의 변이 남을 때까지 각 단계의 그래프가 모두 최소비용 생성나무를 포함한다고 가정한다.
알고리즘의 마지막 단계로 n-1개의 변이 남은 그래프인 생성나무가 최소비용 생성나무를 포함함을 보임으로써 결과로 나온 생성나무가 최소비용임을 보인다.  n개의 변이 남았을 때, 그래프를 F라 하고 F가 포함하는 최소비용 생성나무를 T라고 하자. 그리고 F에서 변 e를 제거하여 알고리즘이 끝난다고 하자. T가 나무이고 회로를 가지지 않으므로 n-1개의 변을 가진다. F에서 변 f를 제거하면 T가 된다고 하자. 알고리즘에서 최대 가중치를 가진 변을 제거하므로 e의 가중치는 f 이상이다. 그러므로 F-e는 T의 비용 이하의 생성나무이다. 그런데 T는 최소비용 생성나무이므로 F-e는 T와 비용이 같다. 즉 F-e는 최소비용 생성나무이고 자신을 포함한다.