Let $G$ be a graph with $n$ vertices, $\delta(G)$ be the minimum degree of any vertex in $G$, and let $\kappa(G)$ be the size of the minimum vertex cutset, or its vertex connectivity.
Show that if $\delta(G) \geq n – 2$, then $\kappa(G) = \delta(G)$.
I am able to show the case for when $\delta(G) = n – 1$, in which case it's just a complete graph, and it's easy.
But when I try to do the case when $\delta(G) = n – 2$, I am able to get as far as:
If we choose a vertex $v$ such that $\deg(v)=n-2$, then it is not directly connected to exactly one other edge $w$, and similarly for $w$. This means that if we remove all vertices but $v$ and $w$, we would increase the number of connected components by 1, but how do I show that this is the minimum number for all $n$?
Other thoughts are: for $n > 4$, there might be exactly two vertices $v$ and $w$ but I don't know how to prove this or find a counter example.
Any help would be appreciated.
Best Answer
For the case when $\delta(G) = n-2$, notice that every induced graph of order $3$ or more must be connected, since if $a$ and $b$ are nonadjacent, they are adjacent to every other vertex in the subgraph.
So deleting $n-3$ vertices will never be sufficient to disconnect the graph.