# Find a maximum matching in linear time

I need to describe an algorithm that finds a maximum matching in a given undirected and unweighted graph. The runtime needs to be linear and is a 2-approximation, that is, the matching size (number of edges) should differ from a maximum matching size not more than a factor of two.

The problem I have is coming up with a linear-time algorithm. I know how to find a maximum matching, but this takes polynomial time.

• What algorithm design paradigms have you tried? You might find that the algorithm is simpler than you have expected. – D.W. Oct 16 '16 at 0:59
• cs.stackexchange.com/q/64915/755 – D.W. Oct 21 '16 at 17:01

Given an unweighted, undirected graph $G=(V,E)$ with $E = \{e_1, \dots, e_m\}$ being our edge set, $e_i = \{v,w\}$ with $v,w\in V$. Furthermore, we have $|E| = m$.
We can create a matching by adding edges greedily. This algorithm is linear in $m$, i.e. $O(m)$.
1. M = $\emptyset$
2. for each edge $e_i \in E$
1. if $M \cup e_i$ form a valid matching, add $e_i$ to $M$
You still need to show that the greedy algorithm above is a 2-approximation. Let $M$ be the solution of the above algorithm and let $M^*$ be the optimal solution. Show that $|M| \leq 2|M^*|$.