2
$\begingroup$

For any simple, connected, undirected graph $G(V,E,w)$ with each carrying distinct positive edge weights, is it true that MST will contain all the edges which do not lie in any cycle of $G$?

I think MST can take any edge of irrespective of the fact whether it is an edge of cycle (like I simply use Kruskal's), Also I am unable to see Why the above statement should true. Can anyone tell how the statement is true?

$\endgroup$
  • $\begingroup$ By the way, all these have nothing to do with whether the edge weights are distinct or not. By the way, an edge that is not in any cycle is called a bridge. So we can say, any MST and in fact, any ST must contain all bridges. $\endgroup$ – Apass.Jack Aug 17 '18 at 21:56
3
$\begingroup$

I think you need to be more precise in your reading of the statement, though it could be better phrased. A different version is "if $e$ is an edge of $G$ and it is not in any cycle in $G$, it must be in any MST of $G$". This doesn't say that edges that are in cycles can't be in the MST, it just says that any edge that isn't in a cycle must be.

To see why this is true, imagine an edge that is not part of a cycle; it has two endpoints, both of which must be part of the MST (otherwise it wouldn't be spanning). So how do we get to those endpoints? If we don't use that edge, we can't reach one of the endpoints (if we could reach both, then the edge would be part of a cycle), thus that edge must be in the MST.

$\endgroup$
1
$\begingroup$

It is simply not true that "MST can take any edge of irrespective of the fact whether it is an edge of cycle (like I simply use Kruskal's)". Think of Prim's Algorithm. Every iteration divides the graph into two sets - $Set A$ always forms a single tree. Each step adds to $tree A$ a light edge that connects A to an isolated vertex in $Set B$ (i.e., set of vertices on which no edge of A is incident).

Now imagine a situation where a vertex of $Set B$ is reachable through only one edge i.e., it is not a part of a cycle. To include it in a spanning tree, that one edge becomes necessary. Hence, every edge not belonging to a cycle should be added, else the vertices incident on the other end (belonging to B) of that edge shall never be included into the spanning tree.

$\endgroup$
  • 1
    $\begingroup$ So it is true... $\endgroup$ – Luke Mathieson Dec 8 '17 at 4:26
  • 1
    $\begingroup$ "I think MST can take any edge of irrespective of the fact whether it is an edge of cycle (like I simply use Kruskal's)" - I was referring to this statetment of OP. $\endgroup$ – Tarun Maganti Dec 8 '17 at 5:57
  • $\begingroup$ Ah, gotcha. Extra characters to make up the minimum length. $\endgroup$ – Luke Mathieson Dec 8 '17 at 5:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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