Skip to main content
edited tags
Link
Source Link

A weaker version of Dirac's theorem

This is related to Dirac's theorem.

For any finite, simple, undirected graph $G=(V,E)$ let $\delta(G)$ denote the minimal degree 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 $M\subseteq E$ such that $$|V\setminus \bigcup M|\leq c.$$