 <p>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.</p> <p>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 <em>every</em> vertex appears in the MST (from the definition of spanning tree).</p> <p>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").</p> <p>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.</p>