If every the sum of the degrees of every pair of nonadjacent vertices exceeds $\left|V(G)\right|+k$, then $\kappa(G)=k+2$. 
Let $ k \in \mathbb{N}$.  Suppose that for every pair of nonadjacent verticles $x,y$ in a graph $G$, $$\deg_G(x) + \deg_G(y) \ge n+k.$$  Prove that $ \kappa \ge k+2$.

Here $n$ denotes the order of $G$ and $\kappa$ denotes the smallest number of vertices to which we can erase so that the graph remains connected.
I am grateful for any help. Does this have something to do with the Ore theorem?
 A: I will proof this for all integers $k\geq -1$. Induction on $k$:


*

*$k=-1$. If $G$ is not connected, then there are at least two components, one of which has at most $\lfloor\frac{n}{2}\rfloor$ vertices, then for $x,y$ in this component:
$$\deg(x)+\deg(y)\leq \lfloor\frac{n}{2}\rfloor-1+\lfloor\frac{n}{2}\rfloor-1\leq n-2$$
a contradiction, so the graph is connected and $\kappa\geq 1 = -1+2$.


For the induction step, we use Menger's theorem, so we want to show that between any pair of nonadjacent vertices there are at least $k+2$ distinct paths.


*

*$k\geq 0$. Pick any two nonadjacent vertices $x$ and $y$ and suppose 
$$\deg_G(x)+\deg_G(y)\geq n+k$$
Define
$$W(x,y) := \{a\in V(G) \mid ax,ay\in E\} \subset V(G)$$
This set is not-empty, since otherwise, if $x$ and $y$ shared no common neighbour, any of the $n-2$ other vertices are adjacent to at most one of $x$ and $y$ so $\deg(x)+\deg(y)\leq n-2$, a contradiction. 
If $|W(x,y)|\geq k+2$, then we have found $k+2$ distinct paths. So, assume $|W(x,y)|\leq k+1$.
Now construct a new graph $G'$ by deleting every vertex of $W(x,y)$. Since each such vertex had at most on edge to $\{x,y\}$, we have
$$\deg_{G'}(x)+\deg_{G'}(y)\geq \deg_G(x)+\deg_G(y)-|W(x,y)|\geq n+k - |W(x,y)|$$
Now, $k - |W(x,y)|\geq -1$ and the induction hypothesis applies, so there are at least $k-|W(x,y)|+2$ distinct paths in $G'$. Now each of those paths is a path in $G$ as well and for each $v\in W(x,y)$, then $xvy$ is a path as well and they are all distinct, so there are $k+2$ distinct paths.
