Optimum of linear program from graph Given a connected (undirected) graph $G$ with vertex set $V$ of size at least $2$, we are allowed to put a real number $x_v$ on each $v\in V$. The constraint is that, for any $W\subseteq V$ such that the induced subgraphs on both $W$ and $V\setminus W$ are connected, $\displaystyle\left|\sum_{v\in W}x_v\right|\le 1$. We want to maximize $\displaystyle\sum_{v\in V} |x_v|$.
Is it true that there is a maximizing solution where all $x_v$'s are integers summing to $0$?
Examples: If $G$ is a path of length $n$, a maximum occurs at $(1,-2,2,-2,\dots,-2,1)$ if $n$ is odd, and $(1,-2,2,\dots,2,-1)$ if $n$ is even.
If $G$ is a cycle of length $n$, a maximum occurs at $(1,-1,\dots,1,-1)$ if $n$ is even and $(1,-1,\dots,1,-1,0)$ if $n$ is odd.
The constraints and objective can be written as a linear program by taking out absolute values, and some linear programming facts may be useful.
 A: Let $G$ be the graph with vertex set $\{1,2,3,4,5\}$ and all edges except $12$. Here, we have a constraint on every subset $W$ except for $W = \{1,2\}$ and its complement $W = \{3,4,5\}$.
The LP optimum is $3$, achieved for example when $x_1 = 1$, $x_2 = \frac12$, and $x_3 = x_4 = x_5 = -\frac12$.
However, if $x_1,x_2,x_3,x_4,x_5$ are all required to be integers, we can't do better than $2$. First of all, $x_i \in \{-1,0,1\}$ for all $i$. Can we have $x_i = x_j = 1$ for some $i,j$? Only if $\{i,j\} = \{1,2\}$, otherwise the $|x_i + x_j| \le 1$ constraint is violated. But if $x_1 = x_2 = 1$, then $|x_1 + x_2 + x_k| \le 1$ for $k=3,4,5$ forces $x_3 = x_4 = x_5 = -1$, and then $|x_3 + x_4| = 2 > 1$. So we can't set two variables to $1$; similarly, we can't set two variables to $-1$. So the optimal integer solution is to set one variable equal to $1$, another to $-1$, and the rest to $0$.
If we do the same thing with $6$ vertices, it appears that the optimal value is $\frac83$, which is not even an integer (achieved by $x_1 = 1$, $x_2 = \frac13$, and $x_3 = x_4 = x_5 = x_6 = -\frac13$).
