# Matching and greedy matching.

The problem is to prove that if $G$ has a perfect matching, then every greedy matching matches up at least half of the nodes.

It is problem 10.4.4 y Lovász, Discrete mathematics. I do not understand his solution to the problem, so I want to check if my argument could work.

The argument that I give is minimal. Consider the bipartite graph with the minimal greedy matching condition. It cannot be the graph where every vertex has degree one, because the greedy algorithm would match the perfect matching.

We have to consider the bipartite graph where in both partitions there are half of the nodes with degree two, and half of the nodes of degree one. This clearly has perfect matching, but the greedy matching could take half of the vertices. Any other bipartite graph with perfect matching is constructed addind edges to this bipartite graph.

• The problem is badly missing context. What "Discrete mathematics"? (Lovasz-Vestergombi, in the version I have it, doesn't have problem 10.4.4.) Is $G$ bipartite? What is a greedy matching? – darij grinberg Dec 28 '16 at 10:50

Consider an edge $\{u,v\}$ of the optimal matching $M_\text{opt}$. Then, because the greedy matching $M_\text{greedy}$ is maximal, at least one of $u$ and $v$ is matched in $M_\text{greedy}$, otherwise we could add $\{u,v\}$ to $M_\text{greedy}$. Thus, $M_\text{greedy}$ matches at least half of vertices incident to $M_\text{opt}$, that is, at least $\frac{1}{2}\cdot 2 \cdot |M_\text{opt}|$ vertices. However, to cover $|M_\text{opt}|$ vertices you need at least $\frac{1}{2}|M_\text{opt}|$ edges in $M_\text{greedy}$ to cover them.
I hope this helps $\ddot\smile$