Maximum independent sets of a bipartite graph

Question

I tried to solve the problem with maximum independent set on bipartite graphs using the greedy method. So I came across this post, which does exactly what I was trying to do. But I concentrate only on dicotyledonous graphs. The counter in the response is not a bipartite graph. Are there any bipartite graphs that this feature does not work?

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 

Why does the greedy algorithm not find the maximum independent set of graph?

Answer 1

The same approach as in the original answer to the question is applicable here, with a slightly modified schedule:

Let's start by removing # 5. What remains is the paw graph (nodes (1,3,4,7)). Remove the leaves in any order. You discover an independent set of four - node: (1,3,5,7)

Start by removing # 6. There is a 4-cycle. Removing any node forces one of these sets:

• (1,3,6)
• (2,4,6)

both are three-element maximal (as in, cannot be extended) independent sets and, therefore, are not maximal (as in the case, as much as possible).