0
$\begingroup$

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.

1 Answers 1

1

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.

  • 0
    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. lol2012-10-31