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

  • 1
    $\begingroup$ 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. $\endgroup$ – Philipp Lampe Aug 7 '18 at 8:27
  • 2
    $\begingroup$ @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. $\endgroup$ – Peter Heinig Aug 7 '18 at 8:46
  • $\begingroup$ @PeterHeinig: I see. Thanks for your explanations. $\endgroup$ – Philipp Lampe Aug 7 '18 at 8:59
  • 1
    $\begingroup$ @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)$. $\endgroup$ – Peter Heinig Aug 7 '18 at 9:31
  • $\begingroup$ (And that bound is best possible in general, as evidenced by a triangle.) $\endgroup$ – Peter Heinig Aug 7 '18 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.