Suppose I have an undirected graph with four vertices $a,b,c,d$ which are connected as in a simple path from $a$ to $d$, i.e. the edge set $\{(a,b), (b,c), (c,d)\}$. Then I have seen the following proposed as a greedy algorithm to find a maximal matching here (page 2, middle of the page)
Maximal Matching (G, V, E):
M = []
While (no more edges can be added)
Select an edge which does not have any vertex in common with edges in M
M.append(e)
end while
return M
It seems that this algorithm is entirely dependent on the order chosen for which edge is chosen first. For instance in my example if you choose edge $(b,c)$ first, then the you will have a matching that consists only of $(b,c)$.
Whereas if you choose $(a,b)$ as your starting edge, then the next edge chosen will be $(c,d)$ and you have a matching of cardinality 2.
Am I missing something, as this seems wrong? I have also seen this described as an algorithm for finding a maximal matching in the context of proving that the vertex cover approximation algorithm selects a vertex cover by choosing edges according to a maximal matching. Any insights appreciated.
