Let $C_n$ denote an undirected simple cycle of $n$ nodes. I want to determine a lower bound on the size of a maximal matching $M$ of $C_n$.
Please note: A subset $M$ of the edges in $C_n$ is called a matching $\Leftrightarrow$ every node $v\in C_n$ is incident to at most one edge in $M$. The matching $M$ is called maximal $\Leftrightarrow$ it cannot be extended to a larger matching by adding an edge which is not already contained in $M$.
Proof: Let $M$ denote a maximal matching in $C_n$. Since
$(v_{2i-1},v_{2i})_{1\le i\le \lfloor\frac{n}{2}\rfloor}$ is a matching in $C_n$, |M| must be greater or equal to $\lfloor\frac{n}{2}\rfloor$.
The Assumption $|M|\ge\lfloor\frac{n}{2}\rfloor +1$ leads to $|\left\{v\in C_n\;|\;\exists w\in C_n : (v,w)\in M\vee (w,v)\in M \right\}|\ge \lfloor\frac{n}{2}\rfloor+2$, contrary to $|C_n|=n$.
Am I missing something or is everything as it should be? I'm a little bit confused, because the exercise only asked for a lower bound.
EDIT:
Okay, I was confused by the terms maximum matching and maximal matching. Let me try to provide a proof for a lower bound of a maximal matching:
I think its easier to construct a maximal matching and show that it can't be reduced while maintaining its maximality.
Let $C_n=(v_0,\dots,v_{n+1})$ with $v_{n+1}=v_0$. Please consider the sequence $S:=(v_{3i},v_{3i+1})_{0\le i\le \lfloor\frac{n}{3}\rfloor -1}$ if $n$ is uneven, extend $S$ by $(v_{n-1},v_n)$. $S$ induces a matching $M$ of $C_n$ with $|M|=\lceil\frac{n}{3}\rceil$.
If $M'$ is also a matching of $C_n$ with $|M'|<|M|$, then there exists an natural number $k\le n-1$ such that neither $v_k$ nor $v_{k+1}$ participates in any edge of $M'$. So, $M'$ cannot be maximal.
Best Answer
A maximal matching can have less than $n/2$ edges. Imagine a $C_6$ with the vertices named in order $a,b,c,d,e,f$. Then, the $ab$ and $ed$ edges form a maximal matching, and here it's $n/3$ edges. So what's the most stupid way of choosing your matching ?
Let $X$ denote the set of vertices of $C_n$ that are incident to an edge of some matching $M$. Then, $|M| = |X| / 2$. So how can you minimize $|X|$ while making $M$ maximal ?
You should be able to do the rest by observing that if $M$ is maximal, then for two adjacent vertices $v_1, v_2$, at least one has to be in $X$, because otherwise you can add the $v_1v_2$ edge in $M$.