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 ____ DS go-ds-1 data-structures tree numerical-answers + – Arjun asked Oct 10, 2016 Arjun 621 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 5 votes 5 votes 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. Kapil answered Oct 13, 2016 • selected Jan 18, 2017 by Kapil Kapil comment Share Follow See all 2 Comments See all 2 2 Comments reply Pranav Kant Gaur commented Jan 20, 2017 reply Follow Share IMO question does not imply a tree with $n$ vertices....it asks for simply any tree. 0 votes 0 votes Shashank Kumar Mishr commented Nov 7, 2017 reply Follow Share how one will come to know that we have to remove 36 edges? 0 votes 0 votes Please log in or register to add a comment.
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 I_am_winner answered Jul 16, 2018 I_am_winner comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes Complete graph. Vertices = 10. So, edges = 10(9)/2 = 45. For a tree of n vertices, it MUST have:- n-1 edges. there's exactly one path between each pair of vertices. So, a tree of 10 vertices has 9 edges. 45 - x = 9. x = 36. JashanArora answered Dec 14, 2019 JashanArora comment Share Follow See all 0 reply Please log in or register to add a comment.