GATE IT 2006 | Question: 11

Question

If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is a

• A. Hamiltonian cycle
• B. grid
• C. hypercube
• D. tree

Comments

MST → TREE

---

yes

---

 

 Reasoning: Minimality and Connectivity

 

To understand why the answer is a tree, we look at the two requirements provided in the problem:

1. Connects all vertices: The subset must provide a path between every pair of vertices in the graph.

2. Minimum total weight: The sum of the weights of the chosen edges must be as small as possible.

Why not a Cycle (Hamiltonian, Grid, or Hypercube)?

A tree is defined as a graph that is connected and acyclic (has no cycles). If a subset of edges contains a cycle, you can remove any one edge from that cycle and the graph will still be connected.

Since the problem states all edge weights are positive, removing that extra edge will always result in a lower total weight. Therefore, any structure with a cycle (like a Hamiltonian cycle a grid, or a hypercube) cannot be the "minimum" weight subset.

---

2. Formal Proof (by Contradiction)

We can prove this property formally using the following logic:

The Theorem:

In an undirected graph $G = (V, E)$ where all edge weights $w(e) > 0$, any subset of edges $S \subseteq E$ that connects all vertices $V$ and has the minimum possible total weight $\sum_{e \in S} w(e)$ is a tree.

The Proof:

1. Assumption: Suppose $S$ is a subset of edges that connects all vertices and has the minimum total weight, but $S$ is not a tree.

2. Property of Connected Non-Trees: If $S$ connects all vertices but is not a tree, it must contain at least one cycle.

3. The Reduction: Let $C$ be a cycle in $S$, and let $e_{uv}$ be an edge in that cycle.

4. Maintaining Connectivity: If we remove $e_{uv}$ from $S$, the graph remains connected because any path that previously used $e_{uv}$ can now go the "long way" around the remaining edges of the cycle $C$.

5. Weight Comparison: Let the new set of edges be $S' = S - \{e_{uv}\}$. The total weight of $S'$ is:

   $$\text{Weight}(S') = \text{Weight}(S) - w(e_{uv})$$

6. The Contradiction: Since all edge weights are given as positive ($w(e_{uv}) > 0$), it follows that:

   $$\text{Weight}(S') < \text{Weight}(S)$$

   This contradicts our initial assumption that $S$ was the subset with the minimum total weight.

7. Conclusion: Therefore, $S$ cannot contain any cycles. A connected graph with no cycles is, by definition, a tree.

---

 

Answer 1

• A. Hamiltonian cycle $\Rightarrow$ This is a cycle. A cycle will not only connect all vertices, it will have $1$ extra edge than necessary. So I can just remove that edge & get better cost "subset of edges" which connect all vertices. So, this is FALSE.
• B. grid $\Rightarrow$ A grid graph has cycles and so this is FALSE for same reason as option A.
• C. Hypercube $\Rightarrow$ A hypercube graph also has cycles. So, this also is FALSE.
• D. Tree $\Rightarrow$ This is answer. We need to have Minimum spanning tree to be exact.
  "If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is a Minimum Spanning Tree". !

(D) is TRUE.

Comments

I agree with the answer but only for this question...

coz "tree" in general does not touch all the vertices..ri8 ? Tree is a subgraph which has no cycle..not necessarily contains "ALL" vertices..

---

@Nitesh here we are asked about a subset of EDGES and not Vertices. So to have all vertices and subset of edges so that weight is minimum, we definitely need to have a tree, an MST to be precise.

Answer 2

Target : Get a subset of edges such that weight is minimum and it connects all vertices.

Since, all weights are positive and we need a subset with minimum weight, then we should avoid cycles, coz we should have only a single path between any pair of vertices in the graph. Having a cycle will unnecessarily add up edge weight and will do no help in accomplishing the target.

This rules out all options A, B and C.

Hence, answer = option D

Answer 3

Tree is a minimally connected Graph.

 So, Option (D) is Correct.

Answer 4

I think it is (D)

Comments

is Hamiltonian Cycle not Possible?why?

Answer 5

A minimum spanning tree is a spanning tree of a connected, undirected graph. It connects all the vertices together with the minimal total weighting for its edges.

answer is D

Answer 6

The correct answer is Tree as explained above.

Now some people may get confused regarding the correctness of this option as a tree may not necessarily connect all the vertices, which is true indeed. However, here we are not asked about the definition of tree. We are just given a scenario where we have a subset of edges that connects all the vertices and has minimum total weight. This is clearly a Minimum Spanning Tree and not any tree in general. However, an MST is still a tree (with some special properties) and so among the given options, Tree is correct. 

Sometimes questions like this are given, where none of the options are 100% correct, so we have to choose the option which is closest to being correct.