# 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.$$

• I have a question concerning your notation $\bigcup M$. Isn't the union of a single set $M$ equal to $M$ itself (which is not a subset of $V$)? Or is this supposed to mean $\bigcup_{m\in M}m$? In this case, the left hand side is equal to the number of vertices that are not covered by $M$. However, the complete bipartite graph $G=K_{n+c+1,n}$ has $\delta(G)=n$ but every matching leaves at least $c+1$ vertices in the large independent set uncovered. Aug 7, 2018 at 8:27
• @PhilippLampe: $\bigcup M$ obviously means the union of a set as it 'Axiom of Union' in the ZF-axioms (en.wikipedia.org/wiki/Axiom_of_union). The OP's notation is correct. Re "equal to $M$ itself": no, that would be the equation $\bigcup\{M\} = M$. Regarding the substance of the question: I think your comment answers the question in the negative. Technically, this would merit making it an answer, though of course this depends on your taste regarding answering easy question. Aug 7, 2018 at 8:46
• @PeterHeinig: I see. Thanks for your explanations. Aug 7, 2018 at 8:59
• @the OP: it's worth pointing out that the size of the smallest maximal matching has been studied in the literature, rather rarely. E.g. Vesna Andova, František Kardoš, Riste Škrekovski: Sandwiching Saturation Number of Fullerene Graphs. MATCH Commun. Math. Comput. Chem. 73 (2015) . (arxiv.org/abs/1405.2197) have some results for fullerene-graphs (they mention the general fact that any graph $G$ has a maximal matching of size $\frac{n-\alpha(G)}{2}$). Since $\alpha\leq n-\delta$ in general, it follows that any graph has a maximal matching of size $\geq\frac12\delta(G)$. Aug 7, 2018 at 9:31
• (And that bound is best possible in general, as evidenced by a triangle.) Aug 7, 2018 at 9:33

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.