Is it possible for a maximum weight edge of a cycle being included in MST?

Question

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.

Answer 1

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.

Answer 2

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