Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Kruskal's algorithm proof of claim 1

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.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.