spanning tree including maximum weight [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

Closed 8 years ago.

Improve this question

Let G be a weighted undirected graph and e be an edge with maximum weight in G.Suppose there is a minimum weight spanning tree in G containing the edge e.Which of the following statements is always TRUE?

a.There exists a cut in g having all edges of maximum weight

b.There exists a cycle in G having all edges of maximum weight

c.Edge e can not be contained in a cycle

d.All edges in G have the same weight

Is a previous year exam questing .i am having trouble to under stand it can any one explain it to me .

Answer 1

The bottom three are false, and the following simple graph is a counter-example to all three:

     1
  a --- b
  |    /
2 |   /
  |  / 2
  | /
  c

Any minimum-weight spanning tree contains either the edge <a,c> or the edge <b,c>. In either case, it is easy to check that (b), (c), and (d) all fail.

Edit: (a) is true. Here is a proof:

Let e be an edge of M which is of maximum weight in G, and let M be a minimum-weight spanning tree for G containing the edge e. If the edge e cuts the graph G, then (a) is obviously true. So, let G' be obtained from G by removing the edge e, and suppose G' is connected.

Let M' be obtained from M by removing the edge e. Now we know that M' consists of two components, because M is a tree, and removing one edge from a tree disconnects it into two components. Furthermore every vertex of G' belongs to M', and G' is connected, so we can obtain a spanning tree of G' by adding a single edge of G' to M'. I claim that every such edge is of maximum weight in G.

To see why, suppose there is an edge e' in G' which connects the two components of M', but is of sub-maximal weight in G. Then, we could remove the edge e from M (our original spanning tree), add this edge e' to M to obtain a new spanning tree of G, but it would be of total weight less than that of M, contradicting the minimal-weight of M.

So, consider the set of all edges of G' which connect the two components of M'. These edges together with e form an edge-cut-set of G, and all must be of maximal weight in G.

Answer 2

Let's start from the simple ones - d is wrong - take any MST, and reduce one of the weights to some unique new value in some edge (not e) - it's still an MST, but not all edges have the same weight

c is false - if e was heavier that any other edge it would have been true because if it was in a cycle, you could have removed e from the MST (and if required for connectivity - pick any other edge instead and receive a lighter MST). However, e can be in a cycle if the alternative edges are all of the same weight.

b is false - say e is the heaviest, but not in a cycle, just connects the graph to some remote vertice (that isn't connected otherwise).

a - i'm not sure if you meant that the cut is max weight or all the edges of max weight are there (that's not the same thing), please clarify