Consider the following algorithm for the maximum matching problem:
- Sort all nodes by their $\deg(v)$
- Take the node with minimal $\deg(v)$
- Take a random edge $(u,v)$ $\in$ $E$
- Add $(u,v)$ to $M$
- 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?