Log In
25 votes

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

  1. Hamiltonian cycle
  2. grid
  3. hypercube
  4. tree
in Graph Theory 2.6k views

8 Answers

45 votes
Best answer
  1. 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.
  2. grid $\Rightarrow$ A grid graph has cycles and so this is FALSE for same reason as option A.
  3. Hypercube $\Rightarrow$ A hypercube graph also has cycles. So, this also is FALSE.
  4. 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.

edited by

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.
8 votes

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

4 votes

I think it is (D)

is Hamiltonian Cycle not Possible?why?
4 votes

Tree is a minimally connected Graph.

 So, Option (D) is Correct.

3 votes

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

0 votes
The question is talking about minimum spanning tree so D.
0 votes

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.

–1 vote
Answer: D

Related questions

41 votes
5 answers
Consider the undirected graph $G$ defined as follows. The vertices of $G$ are bit strings of length $n$. We have an edge between vertex $u$ and vertex $v$ if and only if $u$ and $v$ differ in exactly one bit position (in other words, $v$ can be obtained from $u$ by flipping a single bit). ... $\left(\frac{1}{n}\right)$ $\left(\frac{2}{n}\right)$ $\left(\frac{3}{n}\right)$
asked Oct 31, 2014 in Graph Theory Ishrat Jahan 4.2k views
29 votes
5 answers
The $2^n$ vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of $G$ are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of connected components in $G$ is: $n$ $n + 2$ $2^{\frac{n}{2}}$ $\frac{2^{n}}{n}$
asked Apr 24, 2016 in Graph Theory jothee 3.3k views
24 votes
2 answers
Let $G$ be a simple graph with $20$ vertices and $100$ edges. The size of the minimum vertex cover of G is $8$. Then, the size of the maximum independent set of $G$ is: $12$ $8$ less than $8$ more than $12$
asked Sep 21, 2014 in Graph Theory gatecse 3.4k views
39 votes
2 answers
Let $G$ be a directed graph whose vertex set is the set of numbers from $1$ to $100$. There is an edge from a vertex $i$ to a vertex $j$ iff either $j = i + 1$ or $j = 3i$. The minimum number of edges in a path in $G$ from vertex $1$ to vertex $100$ is $4$ $7$ $23$ $99$
asked Nov 4, 2014 in Graph Theory Ishrat Jahan 3.8k views