3 votes 3 votes Consider the graph $G$ with $4$ vertices. Its adjacency weight matrix is shown below. Which of the following is true? $$G = \begin{bmatrix} 0&1&1 &1 \\ 1 & 0 & 1 & 1 \\ 1 & 1& 0 & 1 \\ 1&1&1&0 \end{bmatrix}$$ Graph $G$ has no minimum spanning tree Graph $G$ has a unique minimum spanning trees of cost $3$ Graph $G$ has $4$ distinct minimum spanning trees, each of cost $2$ Graph $M$ has $16$ distinct minimum spanning trees, each of cost $3$ Algorithms go2025-algorithms-2 minimum-spanning-tree + – gatecse asked Sep 7, 2020 gatecse 177 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 3 votes 3 votes The given graph is a complete graph with $4$ vertices and so it can have $4^{4-2} = 16$ spanning trees. Since all the edge weights are $1,$ all the $16$ spanning trees are minimum spanning trees with total weight $3.$ gatecse answered Sep 7, 2020 • selected Sep 3, 2022 by Arjun gatecse comment Share Follow See 1 comment See all 1 1 comment reply pritishc commented Jan 14, 2021 reply Follow Share Since the vertices are not labeled and all the edge weights are the same, won’t the 16 min. spanning trees degenerate to just 2 (star and 3-node-path forms) distinct non-isomorphic min. spanning trees? 0 votes 0 votes Please log in or register to add a comment.
