edited by
15,225 views
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

  1. $k$ and $n$
  2. $k-1$ and $k+1$
  3. $k-1$ and $n-1$
  4. $k+1$ and $n-k$
edited by

5 Answers

–3 votes
–3 votes
Lower bound k-1 ,upper bound n-k.
Answer:

Related questions

55 votes
55 votes
6 answers
1
44 votes
44 votes
5 answers
2
8 votes
8 votes
3 answers
3
go_editor asked Jun 15, 2016
3,398 views
A simple graph ( a graph without parallel edge or loops) with $n$ vertices and $k$ components can have at most$n$ edges$n-k$ edges$(n-k) (n-k+1)$ edges$(n-k) (n-k+1)/2$ e...
7 votes
7 votes
3 answers
4
go_editor asked Jun 15, 2016
5,337 views
In a graph $\text{G}$ there is one and only one path between every pair of vertices then $\text{G}$ is aPathWalkTreeCircuit