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.