What graph's minimum vertex cover equals twice the maximum matching?

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.
• I don't understand why $G$ can't have a independent set larger than $k$. – phantom May 2 '20 at 6:06
• @allfaker By definition of $k$. – Fedor Petrov May 2 '20 at 9:48