Consider the following ‘greedy’ algorithm which finds a matching in a graph $G$ in several steps as follows. In each step we pick an edge $xy$ of the graph and add it to the matching constructed so far to obtain a bigger matching. We then delete the vertices $x$ and $y$ and continue with the subgraph thus obtained.

Suppose that $e(G)\ge 1$. Show that the algorithm produces a matching with at least $\frac{e(G)}{2\Delta(G)-1}$ edges.

$e(G)$ is the number of edges in $G$.

$\Delta(G)$ is the maximum degree of $G$.

I have tested the algorithm with some graphs but am unsure how I would go about showing that a matching is produced with at least $\frac{e(G)}{2\Delta(G)-1}$ edges.

Any help would be appreciated.


1 Answer 1


The required inequality can be proved by induction with respect to the number $n$ of vertices of the graph (we drop condition $e(G)\ge 1$). Indeed, it is easy to check it when $n\le 2$. Suppose that the inequality is already proved for all numbers $n\le n’$ and let the graph $G$ has $n'$ vertices. When we delete the vertices $x$ and $y$, we also delete at most $2\Delta(G)-1$ edges. By the inductive hypothesis, the algorithm applied to the remaining graph yield us a matching with at least $$\frac {e(G)-(2\Delta(G)-1)}{2\Delta(G)-1}=\frac {e(G)}{2\Delta(G)-1}-1$$ edges. Adding to it the edges $xy$ we obtain a matching with at least $\frac {e(G)}{2\Delta(G)-1}$ edges.

  • $\begingroup$ I'm not sure what my induction step or hypothesis would be in this case. I would very much appreciate if you could clarify for me what they are. $\endgroup$
    – MathDeg
    Nov 12, 2017 at 16:22
  • $\begingroup$ @MathDeg Done.. $\endgroup$ Nov 12, 2017 at 16:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .