# A problem with the greedy approach to finding a maximal matching

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.