Show that if $S$ is a vertex cut of cardinality $\kappa (G)$, then $G-S$ has at most $t$ components

Question

Let $G$ be a non-complete graph of order $n$ and connectivity $k$ such that for every $v\in V(G)$, $deg(v) \geq \frac{n+kt-t}{t+1}$ for some $t \geq 2$. Show that if $S$ is a vertex cut of cardinality $\kappa (G)$, then $G-S$ has at most $t$ components

For this problem, I didn't get very far

Since $G$ be a non-complete graph of order $n$ and connectivity $k$, $|S| \geq k$. I tried to prove this by induction. So

Base : $t=2$. Show that for every $v\in V(G)$, $deg(v) \geq \frac{n+2k-2}{3}$, $G-S$ has at most $2$ components.

However, I can't see how the degree of $V$ can help me complete the base, left alone the inductive step.

Answer 1

HINT: do not use induction.

1. Assume that $G-S$ has more than $t$ components.

2. Use the pigeon hole principle to find a component $C$ of $G-S$ that has a small number of vertices.

3. Draw a conclusion about the degree of the vertices in $C$.

4. Then draw a conclusion about the degree of those vertices in $G$.

5. Reach a contradiction with the degree assumption of the problem.

Ad 2.: $G-S$ has $n-k$ vertices. If it has more than $t$ components, it has at least $t+1$ components. Then the pigeon hole principle says there is at least one component with at most $\frac{n-k}{t+1}$ vertices (if every component would have more than $\frac{n-k}{t+1}$ vertices then $G-S$ would have more then $(t+1)\frac{n-k}{t+1}=n-k$ vertices).