Minimum spanning tree of a connected induced subgraph

Question

I'm doing an online course in which I'm struggling with the following multiple-choice question:

Suppose $ T $ is a minimum spanning tree of the connected graph $ G $. Let $ H $ be a connected induced subgraph of $ G $. (I.e., $ H $ is obtained from $ G $ by taking some subset $ S \subseteq V $ of vertices, and taking all edges of $ E $ that have both endpoints in $ > S $. Also, assume $ H $ is connected.) Which of the following is true about the edges of $ T $ that lie in $ H $? You can assume that edge costs are distinct, if you wish. [Choose the strongest true statement.]

• For every $ G $ and $ H $, these edges form a minimum spanning tree of $ H $
• For every $ G $ and $ H $, these edges are contained in some minimum spanning tree of $ H $
• For every $ G $ and $ H $ and spanning tree $ T_H $ of $ H $, at least one of these edges is missing from $ T_H $
• For every $ G $ and $ H $, these edges form a spanning tree (but not necessary minimum-cost) of $ H $

I don't understand why option 4 is not correct; the hint given is as follows:

Suppose G is a triangle and H is an edge.

Suppose that G is a triangle with nodes 1, 2, and 3, all connected, and we choose the subgraph H from nodes 1 and 2, thus including only the edge (1,2). That edge then forms a minimum spanning tree of those two nodes, no?

Incidentally, the answer

For every G and H, these edges for a minimum spanning tree of H

is also incorrect.

Answer 1

Suppose that $G$ is the triangle on $\{1,2,3\}$ (with arbitrary edge weights), that $T$ is $\{\{1,2\},\{1,3\}\}$ (without loss of generality), and consider $H = \{\{2,3\}\}$, which is induced by $S = \{2,3\}$. No edges of $T$ lie in $H$, and in particular these edges do not constitute a spanning tree of $H$.

Answer 2

Consider a triangle graph $ G = C \xleftarrow{3} A \xrightarrow{1} B \xrightarrow{1} C; \therefore T = {(A, B), (B, C)} $. If $ H = {(A, C)}, T \cap H = \emptyset $, which rules out the options claiming $ T \cap H $ forms a spanning tree.

These edges are contained in some minimum spanning tree of $ H $. To prove it, let's establish the Light-Edge Property of a MST.

Light-Edge Property: Let G = (V, E) be a connected undirected weighted graph with distinct edge weights. For any cut of G, the minimum weight edge that crosses the cut is in the minimum spanning tree T of G.

Proof: Suppose $ e(v, w) \in E, e \notin T $ be the minimum weight edge. If we take a cut $ (A, B) \text{ s.t. } v \in A, w \in B $, then there must be another edge $ e' \in T, e' \neq e $ that connects $ v $ and $ w $ (since by definition $ T $ is a connected subgraph). Let $ T' = T - \{e'\} \cup \{e\} $; since, $ weight(e') > weight(e), weight(T') < weight(T) $. Since $ T $ is a MST, this brings us to a contradiction, and hence $ e \notin T $ cannot be true.

Back to the original question, suppose $ T' $ be a MST of $ H $ and an edge $ e \in T \cap H, e \notin T' $. Arguing on the same lines as the Light-Edge Property, we can show that this contradicts the assumption $ T $ is a MST, and $ e $ must be in $ T' $. Since $ e $ is an arbitrary edge, all edges in $ T \cap H $ must be included in $ T' $.

The solutions to the other questions from the course are available on my blog.