Given a graph G, why is following greedy algorithm not guaranteed to find maximum independent set of G:
Greedy(G):
S = {}
While G is not empty:
Let v be a node with minimum degree in G
S = union(S, {v})
remove v and its neighbors from G
return S
I am wondering can someone show me a simple example of a graph where this algorithm fails?