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.
