1
$\begingroup$

(1) Let's say $T_1$ has $r$ number of edges and $T_2$ has $s$ number of edges; where $r \ne s$ but two trees has same weight since they both are MST.

I kind feel this kind not be true because to span $n$ vertices with minimum number of edges, we need $n-1$ edges. so MST must have at least $n-1$ edges; if some MST has more than $n-1$ edges, then there must exists a cycle which leads to non-MST.

However, I don't know how to show that if the number of edges is greater or equal to the number of vertices of an an undirected, connected graph $G$, then $G$ has a cycle.

What if the graph is directed? Is this hold as well?

Any hint?

$\endgroup$
0

1 Answer 1

4
$\begingroup$

The answer is no. When running an algorithm for finding MST, It is first of all a tree, it has |v| - 1 edges $exactly$.

If there are more than |v| - 1 edges, than there're two vertices that their path isn't simple, which is simply shown with induction. Meaning if there's a path from s to t with more than |v| - 1 edges, one of the vertices will be repeated.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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