Let $G=(V,E)$ be a connected simple undirected graph and let $k>0$ be an integer such that


1. $\delta(G) \geq k$ (that is every vertex has at least $k$ neighbours), and
2. $K\_{k+1}$ is not a minor of $G$.


**Question:** In terms of $k$, how many vertices does a graph satisfying 1. and 2. above to contain at least? In other words, I am looking for an interesting lower bound for $|V|$.


(Remark: a trivial lower bound for $|V|$ is $|V|\geq k+2$ as for $|V|=k+1$ we would get $G\cong K\_{k+1}$ by point 1 above, violating point 2.)



Lower bound for number of vertices in graph with certain forbidden minor
There is such a graph with $k+2$ vertices for all $k \geq 4$. To see this, first assume that $k$ is even. Let $G$ be $K\_{k+2}$ minus the edges of a perfect matching. Note that every vertex of $G$ has degree $k$, but $G$ does not contain a $K\_{k+1}$-minor. For $k$ odd, just take the even example and add an apex vertex. 


