What is the size of a maximum matching in a cycle of length $2k + 1$:
$$\large v_1, v_2,..v_{2k+1}$$
What is the size of a minimum vertex cover?
I know that If $G$ is a bipartite graph, then the maximum size of a matching in $G$ equals to the minimum size of a vertex cover in $G$. I am not sure on how to go on after this for a cycle of length $2k+1$
Best Answer
The size of a maximum matching is $k$.
On one hand, it's easy to find a matching with size $k$.
On the other hand, if you find a matching with size bigger than $k$, then the matching has vertexes not less than $2k+2$ as no vertex are in two edges of the matching. But the cycle has $2k+1$ vertexes only. The contradictory occurs.
The size of a minimum vertex cover is $k+1$.
On one hand, it's easy to find a vertex cover with size $k+1$.
On the other hand, if you find a vertex cover with size smaller than $k+1$, then it covers at most $2k$ edges as one vertex covers at most $2$ edges. But the cycle has $2k+1$ edges. The contradictory occurs.