# Kruskal's algorithm proof

I'm having trouble understanding part of the proof of Kruskal's algorithm. In the notes that our professor gave us, he has this:

Ok so this is missing some things. Unfortunately the lecture does not have any audio and I'm stuck with the notes and just a video of him writing this proof. I am going to talk to him, but that won't be until Tuesday. I was curious if someone could help me understand this beforehand. Basically this is the proof of the claim that the number of vertices in the result of Kruskal's algorithm is the same as the original graph's vertices.

I am thinking this is a proof by contradiction? We assume that the statement is V(T*)!=V(G) and so we show X1=V(T*) and X2=V(G)-V(T*), and somehow...(adding another vertex and another edge that does not exist into there causing a contradiction? This is the last page on the notes so there isn't anything else neither on the video either. Any help? Thanks in advance.

-

OK, so you're interested in the claim that every vertex of $G$ shows up in the tree created by the algorithm. That's what my answer is about, no? When the algorithm terminates, there can't be a vertex of $G$ missing from the tree, because as long as there's a vertex of $G$ missing from the tree there's an edge joining a vertex in the tree to a vertex not yet in the tree, and as long as that's the case the algorithm doesn't terminate. – Gerry Myerson Oct 30 '12 at 2:52