How to prove that a vertex is in a minimum weight subtree?

Question

This is the problem I have: We have a graph $G$.
$G$ is a connected and weighted graph.
$e$ is one of the edges with the smallest weight in $G$.

How do I prove that $e$ is also in some of the minimum weight subtrees of $G$?

Answer 1

This follows from the correctness of Kruskal's algorithm. The very first step in Kruskal's algorithm is adding the edge of minimum weight.

Answer 2

Assuming that the edge weights are unique, you know that e must be part of minimum weight subtrees of G because of the "cut property".

The cut property essentially says that it is always safe to add the edge of lightest weight across any cut, as long as there doesn't already exist an edge across that cut.

A cut is defined as any partition of the vertices of graph G into two subsets, namely S and V - S.

This property is the basis for proving the correctness of Kruskal's algorithm and Prim's algorithm.

So since you know that your edge e is the lightest weight edge in your graph G, thanks to the cut property, we know that edge e will be included in those minimum weight subtrees.