Consider an (a, b) graph G (ie a graph with a vertices and b edges). Let k (G), the minimum amount of vertices that can be removed to disconnect the graph, be n>=1.
What would be the possible effects on k(G) of removing one vertex or one edge from G?
I know k(G)<=delta(G) (the minimum degree of all vertices in G), but is this relevant? Removing either an edge or vertex will reduce delta(G) by one if it is incident to the vertex of minimum degree, but this is only relevant if k(G)=delta(G) and doesn't dictate how much it would reduce k(G) by.
Best Answer
Removing a vertex could reduce the connectivity by one or leave it unchanged. The easiest way to show this is to give examples like the ones Leen has given. It's hopefully clear from the definition of connectivity that it couldn't reduce it by any more than that.
But it could also increase the connectivity:
Consider $K_{n+1}$ with an extra vertex $v$ stuck on, adjacent to exactly one vertex $w$ of the $K_{n+1}$. Currently the connectivity is $1$ since removing $w$ disconnects the graph, but if we remove $v$ then we're left with $K_{n+1}$, which has connectivity $n$.
As an extension we could connect $v$ to $k<n$ vertices. Then $G$ is $k$-connected but $G-v$ is $n$-connected.
So $\kappa(G-v)$ can be whatever we like provided it's at least $\kappa(G)-1$.