# Show that the following algorithm doesn't always find the optimal matching

Consider the following algorithm for the maximum matching problem:

1. Sort all nodes by their $\deg(v)$
2. Take the node with minimal $\deg(v)$
3. Take a random edge $(u,v)$ $\in$ $E$
4. Add $(u,v)$ to $M$
5. Delete all edges of $u$ and $v$ in $E$

I have to show that the algorithm isn't correct for undirected graphs with maximum degree 3. (It does find the maximum matching if the maximum degree is 2.)

To prove that the algorithm does not find a maximal matching for a graph $G$, I have to give a counterexample.

My problem is that I am drawing and drawing graphs, but the algorithm is always able to find the optimal matching. Could somebody help me to find a graph where the algorithm cannot find the optimal matching?

• As usual, a good strategy for dealing with this is random testing. In other words: implement the candidate algorithm; implement a "golden-reference" algorithm that is known to always give the correct solution; and try generating 1 million random small graphs and comparing what output the two algorithms give on each one. If you find any graph where they give a different answer, then you have answered your own question. – D.W. Dec 5 '16 at 17:56
• ... sorry but the algorithm clearly fails... it removes a single edge, hence you can just take a graph with a few more edges than necessary and use that as a counter-example. You probably forgot to say to repeat all 5 steps until some condition (which one?) holds... – Bakuriu Dec 5 '16 at 19:52