Question

Any subset of edges that connects all the vertices and has minimum total weight, if all the edge weights of an undirected graph are positive is called _______

(a) subgraph

(b) tree

(c) hamiltonian cycle

(d) grid

I have been asked this question in an interview.

This key question is from Complete and Connected Graphs topic in division Graphs of Discrete Mathematics

Answer 1

Right choice is (b) tree

Easy explanation: If all the edge weights of an undirected graph are positive, any subset of edges that connects all the vertices and has minimum total weight is termed as a tree. In this case, we need to have a minimum spanning tree need to be exact.