0
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 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
    Commented Aug 7, 2018 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
    Commented Aug 7, 2018 at 8:46
  • $\begingroup$ @PeterHeinig: I see. Thanks for your explanations. $\endgroup$
    – Philipp Lampe
    Commented Aug 7, 2018 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
    Commented Aug 7, 2018 at 9:31
  • $\begingroup$ (And that bound is best possible in general, as evidenced by a triangle.) $\endgroup$
    – Peter Heinig
    Commented Aug 7, 2018 at 9:33

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .