From a complete graph, by removing a maximum of ____ edges, we can construct a…
2018
From a complete graph, by removing a maximum of ____ edges, we can construct a spanning tree.
- A.
e−n+1
- B.
n−e+1
- C.
n+e−1
- D.
e−n−1
Attempted by 381 students.
Show answer & explanation
Correct answer: A
A spanning tree with nnn vertices has exactly n−1 edges.
A complete graph has e edges (given).
Maximum edges removable = total edges − edges in spanning tree
e - (n-1) = e - n + 1