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.

-
add comment

1 Answer

I think what's going on here is the following. You have a connected graph, and you are trying to build a spanning tree, and you have gotten partway through. If there are any vertices not yet included in your tree, then there must be an edge joining some vertex that is in your tree to some vertex that isn't yet in your tree (here is where you are using the hypothesis that your graph is connected). So, add that edge to your tree. Since you can always do this, so long as there is a vertex not in your tree, it follows that when the algorithm terminates, there are no vertices not in your tree. That is, every vertex is in your tree, so it's a spanning tree.

-
This doesn't sound correct for what I am looking for. I have the full proof, minus this one part (the first part that my professor chose to prove) that's basically (as stated in my question) that V(T*)=V(G) where T* is the output of Kruskal's algorithm and G is the original graph. I'm starting to think that this graph was related to the next claim which I have that and understand it....T* is connected. The last part I'm still studying it is that T* is a w-min spanning tree. So he uses all of these claims to do the full proof.I'm interested (again like I stated in my question)in the first claim –  pqsk Oct 30 '12 at 2:44
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
Okay. I think I read it too fast...it was late and I've been working so much, but I spoke with my professor today and I am reviewing your answer so yes you're right. Thanks. Although I do enjoy my professor's explicit explanation better though..lol, but then again he is the graph theorist. lol –  pqsk Oct 31 '12 at 0:02
add comment