If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and...

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

Accepted Answer

tree A minimum-weight spanning connector must keep all vertices connected at the lowest total cost. If it contained a cycle, we could remove one edge from that cycle -- since all weights are positive, this saves positive cost while the graph remains connected (the rest of the cycle provides an alternate path). This contradicts minimality. So the connector is acyclic. A connected acyclic graph is a tree. This is exactly the definition of a Minimum Spanning Tree (MST).

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