1 votes 1 votes Let G be a connected graph with 7 connected components and each component is a tree. If G has 26 edge then number of vertices in G is? Graph Theory graph-theory graph-connectivity + – dan31 asked Nov 6, 2018 edited Nov 6, 2018 by dan31 dan31 1.4k views answer comment Share Follow See all 24 Comments See all 24 24 Comments reply Mk Utkarsh commented Nov 6, 2018 reply Follow Share Can someone help me with definition of component? 0 votes 0 votes Utkarsh Joshi commented Nov 6, 2018 reply Follow Share Assume each component is having n1,n2,n3,n4,n5,n6,n7 vertices. Since each component is a tree, n1-1 + n2-1 + n3-1 + n4-1 + n5-1 + n6-1 + n7-1= 26. n1+n2+n3+n4+n5+n6+n7=19. 0 votes 0 votes Mk Utkarsh commented Nov 6, 2018 reply Follow Share bhai connected graph can only have one component as per https://proofwiki.org/wiki/Definition:Component_of_Graph 0 votes 0 votes Dhillu Thambi commented Nov 6, 2018 reply Follow Share minimum of 14 vertices? 0 votes 0 votes Utkarsh Joshi commented Nov 6, 2018 reply Follow Share i did not read the word connected :( 0 votes 0 votes Soumya Tiwari commented Nov 6, 2018 reply Follow Share I'm getting 27 What's the ans given?? 0 votes 0 votes Dhillu Thambi commented Nov 6, 2018 reply Follow Share @utkarsh I think the question is "let G be a simple graph with 7 components". 0 votes 0 votes Mk Utkarsh commented Nov 6, 2018 reply Follow Share Dhillu exactly i feel the same this question is framed incorrectly 0 votes 0 votes Magma commented Nov 6, 2018 reply Follow Share 27 vertices ?? 0 votes 0 votes Mk Utkarsh commented Nov 6, 2018 reply Follow Share A connected graph cannot have more than 1 component 0 votes 0 votes Magma commented Nov 6, 2018 reply Follow Share give small example for explanation This Graph is weakly connected graph 4 component : {1,2} {3 ,2} , {3,4} , {5,4} 0 votes 0 votes Mk Utkarsh commented Nov 6, 2018 reply Follow Share Magma I'm still unable to figure out where i'm wrong Graph G is connected and contain 26 edges now Question mentions there are 7 components Now i checked 3-4 sources for definition and i found that a disconnected graph can have more than one components 0 votes 0 votes Magma commented Nov 6, 2018 reply Follow Share Mk Utkarsh yeah you're right...question is wrong..it's unable to find the no of vertices But what I'm say that...the example that I Upload above "That graph is weakly connected graph and also have 4 components " 0 votes 0 votes Dhillu Thambi commented Nov 6, 2018 reply Follow Share @mk utkarsh "A simple graph with n vertices and k components can have at most [(n-k)(n-k+1)]/2 edges." 0 votes 0 votes Mk Utkarsh commented Nov 6, 2018 reply Follow Share Dhillu Thambi yes i know that v = 6, k = 2 now make a a complete graph of 5 edges will have 10 edges another component is isolated vertex so you see graph is not connected. and plug both values in your formula you'll get 10 as answer 0 votes 0 votes Utkarsh Joshi commented Nov 6, 2018 reply Follow Share if G is a disconnected graph then ans would be 19. 0 votes 0 votes dan31 commented Nov 6, 2018 reply Follow Share I have edited the question. 0 votes 0 votes Soumya Tiwari commented Nov 6, 2018 reply Follow Share @Utkarsh With Connected graph it's not possible as it has only one component.But if it's simple graph then also it's not possible I'm unable to get this point. Please explain anyone. 0 votes 0 votes Mk Utkarsh commented Nov 6, 2018 reply Follow Share Soumya Tiwari with simple disconnected graph its possible 0 votes 0 votes Shaik Masthan commented Nov 6, 2018 reply Follow Share @Utkarsh Joshi n1-1 + n2-1 + n3-1 + n4-1 + n5-1 + n6-1 + n7-1= 26. n1+n2+n3+n4+n5+n6+n7=19. it is 26+7 = 33, right? 0 votes 0 votes Utkarsh Joshi commented Nov 7, 2018 reply Follow Share oops :) yes! 0 votes 0 votes Gurdeep Saini commented Nov 15, 2018 i edited by Gurdeep Saini Nov 18, 2018 reply Follow Share i am getting 27 ?? if it is wrong please someone update answer correction after @shaik masthan comment : correct answer is 33 0 votes 0 votes Shaik Masthan commented Nov 18, 2018 reply Follow Share @Gurdeep Saini answer is 33, may this help you https://gateoverflow.in/237427/graph-theory 1 votes 1 votes Gurdeep Saini commented Nov 18, 2018 reply Follow Share thanks @shailk masthan 0 votes 0 votes Please log in or register to add a comment.