in DS
324 views
2 votes
2 votes
Consider a complete graph on 10 vertices. Minimum no. of edge removals required to make a tree out of it will be ____
in DS
by
324 views

3 Answers

5 votes
5 votes
Best answer
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.
selected by
by

2 Comments

IMO question does not imply a tree with $n$ vertices....it asks for simply any tree.
0
0
how one will come to know that we have to remove 36 edges?
0
0
2 votes
2 votes
for complete graph no of edges are nC2

for tree we need (n-1) edges

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

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.

Answer:

Related questions