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?

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

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

3.Edge e can not be contained in a cycle

4.All edges in G have the same weight

i think Option 4 and 1 is correct but which is always true .and what is the meaning of option 3.Can any body remove my confusion ??

  • $\begingroup$ An easy case is if removing $e$ disconnects the graph, and $e$ has weight 2 while the other edges have weight 1. In this case 2 and 4 fail. So 2 and 4 cannot always be true. If $e$ is part of a triangle with all edges of weight 2, with pendant vertices connected by weight 1 edges, then 3 fails. Can you construct a counterexample for option 1? $\endgroup$ – András Salamon Dec 25 '13 at 22:38
  • $\begingroup$ 1 is true always @AndrásSalamon $\endgroup$ – Xax Dec 26 '13 at 7:03

Homework question.

Anyway - about the third option: the question is whether it is possible that an edge with the maximal weight will be on some cycle (one of the cycles in the graph contains the edge e).

It is very easy question.

General hint: Remember that every MST doesn't contain the edge with the maximal weight of every cycle.

Specific hints:

  1. What does it mean if there no cut in g having all edges of maximum weight?

  2. Who said that G contains cycles?

  3. Think about graphs where all the edges have the same weight.

  4. see hint 2.

| cite | improve this answer | |
  • $\begingroup$ it a previous year question on the exam i preparing for .@gari $\endgroup$ – Xax Dec 24 '13 at 15:29

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.