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.



What graph's minimum vertex cover equals twice the maximum matching?
**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.


