LP relaxation of independent set I've tried the following LP relaxation of maximum independent set

$$\max \sum_i x_i$$

$$\text{s.t.}\  x_i+x_j\le 1\  \forall (i,j)\in E$$
$$x_i\ge 0$$

I get $1/2$ for every variable for every cubic non-bipartite graph I tried.


Is true for all connected cubic non-bipartite graphs?
Is there LP relaxation which works better for such graphs?


Update 03/05:

Here's the result of clique-based LP relaxation suggested by Nathan



I've summarized experiments here  Interestingly, there seem to be quite a few non-bipartite graphs for which the simplest LP relaxation is integral.
Non-bipartite connected cubic graphs have the unique optimal solution $x_i = 1/2$; in a bipartite cubic graph you have an integral optimal solution.



Proof: In a cubic graph, if you sum over all $3n/2$ constraints $x_i + x_j \le 1$, you have $\sum_i 3 x_i \le 3n/2$, and hence the optimum is at most $n/2$.

The solution $x_i = 1/2$ for all $i$ is trivially feasible, and hence also optimal.

In a bipartite cubic graph, each part has half of the nodes, and the solution $x_i = 1$ in one part is hence also optimal.

Any optimal solution must be tight, that is, we must have $\sum_i 3 x_i = 3n/2$ and hence $x_i + x_j = 1$ for each edge $\{i,j\}$. Thus if you have an odd cycle, you must choose $x_i = 1/2$ for each node in the cycle. And then if the graph is connected, this choice gets propagated everywhere.