[Solved]: Independent set on cubic triangle-free graphs

Let’s start by proving that the maximum independent set is of size at most $|V|/2$. Let $I$ be an independent set. For each vertex $v$, let $alpha(v)$ be the number of its neighbors in $I$. If $alpha(v) geq 1$, then we know that $v notin I$. Since the graph is cubic, $sum_v alpha(v) = 3|I|$. Since $alpha(v) leq 3$, the number of vertices such that $alpha(v) geq 1$ is at least $|I|$. Hence $|I| leq |V|/2$. When can we have equality? We must have $alpha(v) in {0,3}$, so for each vertex not in $I$, all its neighbors must be in $I$. The converse is also true – for each vertex in $I$, all its neighbors are not in $I$. In other words, the graph must be bipartite. This can be checked in polynomial time.