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.
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.