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 .
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.