Change in the vertex connectivity of a given graph This is a homework problem I am trying to solve:
What impact does the following operations (prove some bounds on the amount of change and provide examples showing that the bounds are tight) has on the vertex connectivity of a graph:
(a) adding a single edge to a graph (without adding vertices),
(b) removing a single edge,
(c) removing a single vertex,
(d) contracting an edge.
so what I have tried is that I have taken a random graph and have tried to see what happens to the vertex connectivity. In 1st case, I observed that when a single edge (without adding vertices) is added depending on where it gets added the vertex connectivity can be increased but it does not decrease. In the 2nd case, removing a single edge might decrease the vertex connectivity i.e make it 0 (like in the case of a star-like structure) same can be seen in the case of removal of a single vertex. I do not much understand contracting an edge. Even though through various examples I can understand what impacts is having but I am unable to prove or find the bounds are tight or not. I do understand a few specific bounds like $k(G)\leq\lambda(G)\leq\delta (G)$. But I still find myself stuck here.
Any help is appreciated.
 A: By Menger's Theorem, a graph $G$ is $k$-connected iff for each pair of vertices, there are $k$ internally-disjoint paths between every pair of distinct vertices $u, v \in V(G)$.  By internally-disjoint, I mean the paths only intersect at their endpoints $u$ and $v$.
Suppose $e$ is an edge between $x$ and $y$ and it's contracted, giving the graph $G'$.  Assume the connectivity of $G$ is $k$.  If $w$ is an vertex or edge of $G$ (other than $e$) denote its image under contraction by $w'$.  Note then that $x' = y'$.
Case 1: First assume neither $u', v'$ is $x'$.  If $P_1, \dots, P_n$ are a maximal family of internally-disjoint paths from $u$ to $v$, then at most two of these paths contain either $x$ or $y$.  Thus the connectivity between $u'$ and $v'$ is reduced by at most one.
The connectivity between $u$ and $v$ is not increased by contraction: Assume BWOC that it is, so there are internally-disjoint paths $P_1', \dots, P_{n+1}'$ from $u'$ to $v'$, with at most one containing $x' = y'$.  If none contained $x'$ then the graph spanned by the paths pulls back homeomorphically, a contradiction, so assume $x' \in P_1'$.  Then the other paths pull back homeomorphically, so it just remains to show that $P_1'$ pulls back to a path that's internally-disjoint from the rest to finish the case.
To do this, let $w'x'z'$ be a subpath of $P_1'$, where the preimages of $w'$ and $z'$ under contraction are $w, z \in G$.  If $wxz$ (or $wyz$) is a path in $G$, then $P_1'$ pulls back homeomorphically to a path $P_1$ from $u$ to $v$ by mapping $x'$ to $x$ (or $y'$ to $y$ respectively), and since it's internally-disjoint from the other $P_j'$ paths so is $P_1$ from the other $P_j$ paths.
If not, then without loss of generality assume $wx, yz \in E(G)$.  Since $xy = e \in E(G)$ the path $wxyz$ is contained in $G$.  Since none of the other $P_j'$ paths contain $x'$ their pullbacks don't contain $x$ or $y$, and since they're internally disjoint from the rest of $P_1'$ they are internally disjoint to the path $P_1 = Q_1wxyzQ_2$, where $Q_1$ is the pullback of $P_1'$ from $u'$ to $w'$ and $Q_2$ is the pullback of $P_1'$ from $z'$ to $v'$.
Thus edge contraction can decrease connectivity by at most one (two triangles connected along an edge gives an example where it does decrease) and does not increase it between vertices not on $e$.
Case 2: Let $u'=x'$ and $v' \neq x'$.  Let $P_j$ be a maximal collection of internally-disjoint paths from $v$ to $x$, and let $Q_j$ be a maximal collection of internally-disjoint paths from $v$ to $y$.  Then at most one of the $P_j$ paths contains $y$ and vice-versa, so the connectivity between $v'$ and $x'$ can be reduced by at most one (within the previous bound).
However - as pointed out in the comments below - it is possible to increase the connectivity here.  For if $v$ has many more paths to $x$ than $y$ (e.g. all paths to $x$ go through $y$ and thus can't be internally-disjoint), then the connectivity can be increased by $|vc(y) - vc(x)|$ where $vc(w)$ is the minimal connectivity between $w$ and any other vertex.  That this (crappy) bound is actually sharp is given by the same example below, namely a complete graph plus one pendant vertex.
Case 3: Suppose $u' = v' = x' = y'$.  In other words, $u = x$ and $v = y$.  Then assume that the connectivity between $x$ and $y$ is $k$, but for every other pair of vertices it is at least $k+1$.  But that's impossible because $e = xy \in E(G)$ so the connectivity between $x$ and $y$ is $|G| - 1$, which is maximal.
Thus if $vc(G)$ denotes vertex connectivity, $vc(G) -1 \leq vc(G') \leq vc(G) + |vc(y) - vc(x)|$.
After having to edit this one like 500 times, please double-check everything in case 2 before handing it in.
A: To think about this problem, instead of starting with an arbitrary graph and trying these operations, I suggest imagining a graph and a cut in the graph and doing these operations. I'll walk you through the reasoning for one of them: removing a vertex.
There are three cases:

*

*If we remove a vertex that's part of the cut, then the number of vertices in the cut goes down by $1$.

*If we remove a vertex that's not part of the cut, then the number of vertices in the cut is not changed.

*An exception: if we remove the last vertex on one side of the cut, then the cut stops being a cut.

Each graph has a lot of different cuts, some of which are the minimum cuts. If the above things happen to every single one of the cuts, then the vertex connectivity could decrease by $1$ (if all minimum cuts ended up in the first case), stay the same (if some minimum cuts are in the second case), or increase arbitrarily (if all minimum cuts end up in the third case, and the next smallest cut is very large).
You should then be able to draw examples of each of these things happening. (For the arbitrary increase, you'll need an infinite family of similar examples to show that the increase can be arbitrary.)

Contracting a vertex is the weirdest operation and it's hard to get intuition for. The cases are going to be if you

*

*contract an edge between two vertices in the cut;

*contract an edge between two vertices not in the cut;

*contract an edge between a vertex in the cut and a vertex not in the cut.

These are actually going to act a lot like deleting a vertex; your examples might look slightly different.
