0
$\begingroup$

Let C be a cycle in a simple connected weighted undirected graph. Let "e" be an edge of maximum weight on C Which of the following is TRUE?

(A) No minimum weight spanning tree contains e.
(B) There exists a minimum-weight spanning tree not containing e.
(C) no shortest path, between any two vertices, can contain e.
(D) None

This was a question for which I gave the answer A because I thought using Kruskal's algo & since the maximum weight edge is lying on the cycle, we will always have an opportunity to select an edge with lesser weight.

$\endgroup$
3
$\begingroup$

The answer to the question in the title, "is it possible for a maximum weight edge of a cycle being included in MST?", is "not necessarily".

The correct answer to the multiple-choice question is (B).

A counterexample to (A): Let $G$ be an triangle with weight $1$, $1$ and $1$. Let $e$ be any edge of $G$.

The answer by raindrop says (A) is correct. However, he/she also points out that "A possible exception is if multiple edges have the same maximum weight, e.g. there are multiple maximum edges on $C$ which qualify to be labeled $e$. In that case, a minimum weight spanning tree may contain $e$". Let me repeat the condition about $e$ in OP's post is Let "$e$" be an edge of maximum weight on $C$. The article "an" in "an edge" does indicate that possibility. Since we are in math or computer science, one counterexample or one exception is enough to prove the fallacy of a statement.

Proof of (B): Let $m$ be an MST of $G$. If $e$ is not in $m$, we are done. Now suppose $e$ is in $m$. If we remove $e$ from $m$ (but do not remove $e$'s vertices), $m$ will be split into two trees, which we name $m_1$ and $m_2$. As a cycle that connect $m_1$ and $m_2$ by $e$, $C$ must also connect $m_1$ and $m_2$ at another edge, which we name $e'$. Then $m_1$ together with $m_2$ and $e'$ is an MST of $G$ that does not contain $e$.

A counterexample to (C): Let $G$ be an triangle with weight 1, 1 and 1. Let $e$ be any edge of $G$. The shortest path between $e$'s two vertices contains one edge, $e$ itself.

(D) is wrong since (B) is correct.

$\endgroup$
2
$\begingroup$

Yes, the answer is A.

Given a connected weighted undirected graph $G$. Let there be a cycle $C$ with $n$ vertices. Let the vertices connected in $C$ be labeled $v_i$. Let there be a maximum weight edge, labeled $e$, where the vertices on either side of $e$ is labeled $v_1$ and $v_n$ respectively.

   2 ---- n-1
  /         \
 /           \
1-------------n
       e

Suppose that the MST for $C$ contained edge $e$. In this case, either edge $v_1v_2$ or edge $v_{n-1}v_n$ has been omitted from the cycle in favor of edge $e$ to produce the MST. However, since edge $e$ is the maximum weight on the cycle, those other edges are guaranteed to have a smaller weight than $e$. In this case the total weight of those spanning trees which omit $e$ will be lower than the weight of our MST. This is a contradiction. Therefore, the MST for $C$ cannot contain edge $e$.

A possible exception is if multiple edges have the same maximum weight, e.g. there are multiple maximum edges on $C$ which qualify to be labeled $e$. In that case, a minimum weight spanning tree may contain $e$.

$\endgroup$
  • $\begingroup$ You essentially say the correct answer is (B) (if there are several edges with the same weight). $\endgroup$ – vonbrand Jul 30 '18 at 17:30

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.