Proof: A graph $G$ has fewer than $k$ components when $\delta{(G)} \gt (n\!-\!k)/k\;$. 
Let $k$ and $n$ be positive integers with $2 \le k \lt n$, and $G$ a simple graph with $n$ vertices. Show that if for the degree of each vertex $v \in V(G)$ we have $d(v) \gt {(n-k)\over k}$, then $G$ contains fewer than $k$ connected components.  

There is a theorem that says every graph with minimum degree $\delta(G) \ge {V(G) \over 2}$ is connected. I thought I'd try a variation on its proof, which goes like:

Let $G$ have $k$ connected components, and $H$ is the smallest one. Then $V(H) \le {n \over k}$. If also $\delta(G) \ge {n-k \over k}$ then $V(H) \ge {n-k \over k} +1 = {n \over k}$. So $V(H)={n \over k}$ and thus all $k$ components must contain ${n \over k}$ vertices. That means that all $k$ components are the full graphs $K_{n/k}$. But $\delta(G) \gt {n-k \over k}$ so each connected component must be larger than $K_{n/k}$.

Is this proof correct?
 A: You've basically got it. Let me offer a few improvements.

Let $G$ have $k$ connected components, and $H$ is the smallest one. Then $V(H) \le {n \over k}$. If also $\delta(G) \ge {n-k \over k}$ then $V(H) \ge {n-k \over k} +1 = {n \over k}$. So $V(H)={n \over k}$ and thus all $k$ components must contain ${n \over k}$ vertices. That means that all $k$ components are the full graphs $K_{n/k}$. But $\delta(G) \gt {n-k \over k}$ so each connected component must be larger than $K_{n/k}$.

To be more general, you should say "Let $G$ have at least $k$ connected components".

Let $G$ have $k$ connected components, and $H$ is the smallest one. Then $V(H) \le {n \over k}$. If also $\delta(G) \ge {n-k \over k}$ then $V(H) \ge {n-k \over k} +1 = {n \over k}$. So $V(H)={n \over k}$ and thus all $k$ components must contain ${n \over k}$ vertices. That means that all $k$ components are the full graphs $K_{n/k}$. But $\delta(G) \gt {n-k \over k}$ so each connected component must be larger than $K_{n/k}$.

This is too strong of a statement. You are only talking about the component $H$, so it's not clear that you can say this about the other components. But really you don't need to talk about the other components. Just get a contradiction in $H$ and later in the proof change $\delta(G) \gt {n-k \over k}$ to $d(v) \gt {n-k \over k}$ for $v \in V(H)$.
