Minimum spanning tree of a connected induced subgraph

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?

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

is also incorrect.

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

• Edge {2,3} does form a spanning tree of H, since a) it connects all the vertices of H, and b) doesn't contain a cycle. It also happens to be the minimal in this example, but that's just a coincidence. Why do you say "in particular these edges do not constitute a spanning tree of H"? Dec 15 '18 at 6:04
• The claim being refuted is that $T$ restricted to $S$ is a spanning tree for $G$ restricted to $S$. Dec 15 '18 at 9:45

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.