[Solved]: Show that the following algorithm doesn't always find the optimal matching

Problem Detail: 

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?

Asked By : M.Mac

Answered By : Yuval Filmus

Consider a graph consisting of two triangles connected by an edge (a total of seven edges). Using this graph, Besser and Poloczek show that no greedy-like algorithm for maximum matching can be optimal even on graphs with maximum degree 3.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/66970