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

Question

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

Answer 1

Consider the following graph:

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.