This is related to [Dirac's theorem](http://en.wikipedia.org/wiki/Dirac%27s_theorem_on_Hamiltonian_cycles#Bondy.E2.80.93Chv.C3.A1tal_theorem).


For any finite, simple, undirected graph $G=(V,E)$ let $\delta(G)$ denote the minimal [degree](https://en.wikipedia.org/wiki/Degree_(graph_theory)) of all vertices.


Are there positive integers $n,c\in\mathbb{N}$ with the following property?



> 
> 
> > 
> > Whenever $G=(V,E)$ is connected and $\delta(G)\geq n$, there is a [matching](https://en.wikipedia.org/wiki/Matching_(graph_theory)) $M\subseteq E$ such that $$|V\setminus \bigcup M|\leq c.$$
> > 
> > 
> > 
> 
> 
> 



A weaker version of Dirac's theorem
No. Suppose that $n$ and $c$ are natural numbers. We consider the complete bipartite graph $G=K\_{n+c+1,n}$. Then $\delta(G)=n$. However, every matching $M$ of $G$ contains at most $n$ edges; hence it leaves at least $c+1$ vertices uncovered.


