65 votes 65 votes Let $\text{G}$ be an arbitrary graph with $n$ nodes and $k$ components. If a vertex is removed from $\text{G}$, the number of components in the resultant graph must necessarily lie down between $k$ and $n$ $k-1$ and $k+1$ $k-1$ and $n-1$ $k+1$ and $n-k$ Graph Theory gatecse-2003 graph-theory graph-connectivity normal isro2009 + – Kathleen asked Sep 16, 2014 edited Jan 24 by makhdoom ghaya Kathleen 15.2k views answer comment Share Follow See 1 comment See all 1 1 comment reply Kiyoshi commented Dec 9, 2021 reply Follow Share Suppose graph $G$$ =$ $N_{n}$ (Null graph of n vertices) then it has n vertices and n components too. Now, remove 1 vertex then left with (k-1) components or (n-1) components. Gives upper and lower bound both...😁 3 votes 3 votes Please log in or register to add a comment.
–3 votes –3 votes Lower bound k-1 ,upper bound n-k. anshu answered Feb 3, 2015 anshu comment Share Follow See all 4 Comments See all 4 4 Comments reply anshu commented Feb 3, 2015 reply Follow Share Because if u remove frm star graph it only has one compo so n-1 but the general case will be n-k for k compo graph. 0 votes 0 votes Arjun commented Jul 22, 2015 reply Follow Share But consider the case where the other components are isolated vertices. 2 votes 2 votes Rupendra Choudhary commented Dec 23, 2017 reply Follow Share Hello anshu , he is asking about maximum possible number of components , which would be n-1 and n-k is supposed to be lesser or equal to n-1. 1 votes 1 votes Anu007 commented Dec 23, 2017 reply Follow Share yes when graph is star graph then components will be n-1 components will be come. 1 votes 1 votes Please log in or register to add a comment.