Algorithms proof regarding minimum spanning tree, Is my answer correct?

Question

This is the questions, i admit this is a homework questions, i am not looking for answers, but rather i want to just know if i am going in the correct direction, and if i am not kindly point me in the correct direction.

Question: Show that if no two edges in a weighted graph have the same weight, then the edge with least weight incident to a vertex v is included in every minimum spanning tree (MST).

My answer: Given a vertex (V) and a weighted graph (G), we note that ∃ (there exists) and edge (E) associated with V, that is the least weighted edge. Note that we will have two distinct vertices that will have the same least weighted edge. This does not represent a problem for us, if one of the vertice is included in the minimum spanning tree, the other will be to. If we started to build a MST, at one instance the least weighted edge has to be included in the MST, since one (or both) of the vertex that has the least edge must be included to obtain a MST ( since the definition of a MST states that we must find the minimum path from a root to all verticies)

I am not so sure if my answer is valid, do you think how i prove it is enough?

Answer 1

Your proof isn't valid, and the reason for that is that there are many imprecise statements in your proof, and some falsehoods. For example you say that "the definition of a MST states that we must find the minimum path from a root to all verticies", whereas the definition of an MST is that it is the spanning tree of minimum weight.

You use the fact that a "vertex that has the least edge" must be in the MST, but it's hard to see the relevance because every vertex appears in the MST (from the definition of spanning tree).

The skill in writing proofs is to be extremely precise in your language, and to make logical steps that follow from things you prove (or if you're applying a well-known theorem, then a good citation). It's extremely important that you know and use the exact definitions of jargon you are using (here, perhaps, "minimal" and "spanning" and "tree").

For this proof, as Keith says, you want to try a proof by contradiction. That is that if there is a spanning tree that doesn't contain the edge of minimal weight then you can find a spanning tree with a lower weight. Perhaps it would help to prove first how many edges a spanning tree must have, and whether every tree in the graph with that number of edges has to be a spanning tree. You should be clear what the definition of a tree is too as it will be needed in the proof: you'll take the spanning tree that doesn't contain the edge, modify it somehow, and show that it has lower weight and is still a spanning tree.

Answer 2

That doesn't sound like a proof to me. You seem to make a leap from the idea that the vertex will be included to the idea that the edge will without proving that it must be. You should probably consider something more along the lines of proof by contradiction.