1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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"? $\endgroup$ – Abhijit Sarkar Dec 15 '18 at 6:04
  • $\begingroup$ The claim being refuted is that $T$ restricted to $S$ is a spanning tree for $G$ restricted to $S$. $\endgroup$ – Yuval Filmus Dec 15 '18 at 9:45
0
$\begingroup$

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.

$\endgroup$

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.