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.