GATE Overflow | Data Structures | Test 1 | Question: 20

Question

Consider a complete graph on 10 vertices. Minimum no. of edge removals required to make a tree out of it will be ____

Answer 1

A tree has N vertices and N - 1 edges .

For a complete graph of 10 vertices having 45 edges,remove 36 edges hence getting a tree.

Comments

IMO question does not imply a tree with $n$ vertices....it asks for simply any tree.

---

how one will come to know that we have to remove 36 edges?

Answer 2

for complete graph no of edges are nC2

for tree we need (n-1) edges

 therefore we need to remove nC2 -(n-1) edges

Answer 3

Complete graph. Vertices = 10. So, edges = 10(9)/2 = 45.

For a tree of n vertices, it MUST have:-

1. n-1 edges.
2. there's exactly one path between each pair of vertices.

So, a tree of 10 vertices has 9 edges.

45 - x = 9.

x = 36.