# looking for counterexample for my algorithm for maximum independent set in Bipartite Graph

We wish to find the maximum independent set in a bipartite graph. My intuition led me to the following algorithm. (Assume that the bipartite graph is connected and has at least 3 vertices, if not run the algorithm on each component)

1. Given $$G=(L,R,E)$$
2. Let $$S$$ be the set of vertices with degree $$1$$. Note that since graph is connected and has at least $$3$$ vertices, $$v,u\in S\implies (v,u)\not \in E$$. (If $$S$$ is empty, go to step $$5$$)
3. Add the vertices in $$S$$ to the independent set. $$\forall s\in S$$, remove $$s$$ and neighborhood of $$s$$ from $$G$$
4. If the graph is connected, repeat steps $$2-4$$. If it is disconnected, repeat the steps $$2-4$$ for each component.
5. if $$|L| > |R|$$, add $$L$$ to the independent set, else add $$R$$

Obviously, the output is some independent set, not necessarily the maximum. However, I could neither prove nor come up with an counter example. Any help will be appreciated.

https://cs.stackexchange.com/a/3033 has a answer which does not rely on intuition

None of the vertices has degree 1, so we go straight to step 5. Your algorithm would return 5 as the maximum independent set size, as both $$L$$ and $$R$$ have 5 vertices. However, the actual maximum independent set is $$\{1, 2, 3, 6, 7, 8\}$$, which has 6 vertices.