###### Question 9849 – Minimum-Spanning-Tree

February 13, 2024###### Question 10669 – Minimum-Spanning-Tree

February 13, 2024# Question 10740 – Minimum-Spanning-Tree

What is the largest integer m such that every simple connected graph with n vertices and n edges contains at least m different spanning trees?

Correct Answer: C

Question 11 Explanation:

If graph is connected and contains n vertices and n edges means there is possibility of only one cycle.

→ If we create a different spanning tree by removing one edge at a time.

→ For cycle required 3 minimum edges. So there is at least 3 spanning trees in such a graph.

→ If we create a different spanning tree by removing one edge at a time.

→ For cycle required 3 minimum edges. So there is at least 3 spanning trees in such a graph.

1

2

3

n

Subscribe

Login

0 Comments