Matching: https://en.wikipedia.org/wiki/Matching_(graph_theory)

Vertex Cover: https://en.wikipedia.org/wiki/Vertex_cover

It is easy to see that

$$\texttt{minimum vertex cover} \leq 2 \texttt{ maximum matching}$$ I want to know that for what kind of graphs the equality is hold in the above inequality.

As an instance, $C_3$ is an example.


Answer. Such a graph $G$ is a disjoint union of odd complete graphs.

Obviously such graphs satisfy the equality $$\texttt{minimum vertex cover} = 2 \texttt{ maximum matching}.\quad (\star)$$

Assume that $G=(V,E)$ satisfies $(\star)$. Denote by $k$ the size of maximal independent set in $G$, then $$k=|V|-\texttt{minimum vertex cover}=|V|-2\cdot\texttt{maximum matching}=\\ \texttt{ minimum number of vertices not covered by a matching}.$$ On the other hand, by Tutte β€” Berge formula, if $k$ is the minimum number of vertices not covered by a matching, then there exists a subset $U\subset V$ such that $G-U$ has $|U|+k$ odd connected components. If $|U|>0$, then taking a vertex from each component we get an independent set with more than $k$ vertices. Therefore $U=\emptyset$, $G$ has $k$ odd components and if $G$ has also an even component, we again may take an independent set with more than $k$ vertices. Also if one of these connected components $C$ is not a complete graph, we may take to not-connected vertices in $C$ and a vertex from each other component, again having too large independent set. That is.

  • $\begingroup$ I don't understand why $G$ can't have a independent set larger than $k$. $\endgroup$ – phantom May 2 '20 at 6:06
  • $\begingroup$ @allfaker By definition of $k$. $\endgroup$ – Fedor Petrov May 2 '20 at 9:48
  • 1
    $\begingroup$ I understand now, I forget the true |𝑉|=πš–πš’πš—πš’πš–πšžπš– πšŸπšŽπš›πšπšŽπš‘ πšŒπš˜πšŸπšŽπš›+πš–πšŠπš‘πš’πš–πšžπš– πš’πš—πšπšŽπš™πšŽπš—πšπšŽπš—πš 𝚜𝚎𝚝 $\endgroup$ – phantom May 2 '20 at 14:52

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.