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

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.
by

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?
for complete graph no of edges are nC2

for tree we need (n-1) edges

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

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.