Given a connected directed graph D, show $\sum_{v\in V_{D}} |deg^{+}(v)-deg^{-}(v)|\le 2(|V_{D}|-1).$

Question

Given a simple connected directed graph $D$, show that:

$$\sum_{v\in V_{D}} |d^{+}_{v}-d^{-}_{v}| \le 2(|V_{D}|-1).$$

$V_{D}$ is the vertex-set and $A_{D}$ is the arc-set of $D$. $d^{+}_{v}$ and $d^{-}_{v}$ are the out-degree and in-degree of vertex $v$.

I have been trying to solve this mostly with the properties that this equality brings $\sum_{v\in V_{D}} |d^{+}_{v}-d^{-}_{v}| = \sum_{v\in V_{D}} max(d^{+}_{v},d^{-}_{v})-min(d^{+}_{v},d^{-}_{v})$. But so far I've been hitting brick walls, so I thought maybe one of you wizards could enlighten me.

Updated on 23.4.2017

Although there's nothing really to add here since the conjecture was disproven. I'd like to prove the actual greatest value $\sum_{v\in V_{D}} |d^{+}_{v}-d^{-}_{v}|$ can have, for some simple connected directed graph.

$(T1)$ $2(\sum_{v\in V_{D}}max(d^+_{v}, d^-_{v})+|V_{D}|-1)\ge \sum_{v\in V_{D}} |d^{+}_{v}-d^{-}_{v}|$.

$(L1)$ If a simple directed graph is connected then $|A_{D}| \ge |V_{D}|-1,$

$(L2)$ $2|A_{D}| = \sum_{v\in V_{D}} max(d^{+}_{v},d^{-}_{v})+min(d^{+}_{v},d^{-}_{v})$.

$(P1)$ Let $D$ be a simple connected directed graph, then

$$|A_{D}| \ge |V_{D}|-1 \tag*{(by P1 and L1)}$$ $$\frac{1}{2}\left(\sum_{v\in V_{D}}max(d^+_{v}, d^-_{v}) + min(d^+_{v}, d^-_{v})\right) \ge |V_{D}|-1 \tag*{(by L2)}$$ $$-|V_{D}|-1\ge -\frac{1}{2}\left(\sum_{v\in V_{D}}max(d^+_{v}, d^-_{v}) + min(d^+_{v}, d^-_{v})\right)$$ $$-2(|V_{D}|-1)\ge \sum_{v\in V_{D}}-max(d^+_{v}, d^-_{v}) - min(d^+_{v}, d^-_{v})$$ $$2\left(\sum_{v\in V_{D}}max(d^+_{v}, d^-_{v})-|V_{D}|+1\right) \ge \sum_{v\in V_{D}}max(d^+_{v}, d^-_{v}) - min(d^+_{v}, d^-_{v})$$ $$2\left(\sum_{v\in V_{D}}max(d^+_{v}, d^-_{v})-|V_{D}|+1\right)\ge \sum_{v\in V_{D}} |d^{+}_{v}-d^{-}_{v}| \tag*{($\therefore P1$) $\blacksquare$.}$$

Let's also prove the trivial greatest value of $\sum_{v\in V_{D}}|d^{+}_{v}-d^{-}_{v}|$, that is $2|A_{D}|$.

$(T2)$ $\sum_{v\in V_{D}}|d^{+}_{v}-d^{-}_{v}| \le 2|A_{D}|$.

$(L3)$ $2|A_{D}| \ge \sum_{v\in V_{D}}max(d^{+}_{v},d^{-}_{v}) \ge |A_{D}| \ge \sum_{v\in V_{D}}min(d^{+}_{v},d^{-}_{v}) \ge 0.$

$$2|A_{D}| \ge \sum_{v\in V_{D}}max(d^{+}_{v},d^{-}_{v}) \tag*{(by L3)}$$ $$2|A_{D}|-\sum_{v\in V_{D}}min(d^{+}_{v},d^{-}_{v}) \ge \sum_{v\in V_{D}}max(d^{+}_{v},d^{-}_{v})-min(d^{+}_{v},d^{-}_{v})$$ $$2|A_{D}| \ge 2|A_{D}|-\sum_{v\in V_{D}}min(d^{+}_{v},d^{-}_{v})\tag*{(by L3)}$$ $$2|A_{D}| \ge \sum_{v\in V_{D}}max(d^{+}_{v},d^{-}_{v})-min(d^{+}_{v},d^{-}_{v}) \tag*{($\therefore P2$) $\blacksquare$.}$$

Answer 1

The following seems to be a counterexample.

Consider a complete bipartite directed graph with partition $A,B$, where $|A|=|B|=n$ (there are all possible edges from $A$ to $B$). Add one additional vertex $c$ and all possible edges from $B$ to $c$ and from $c$ to $A$. Thus obtained graph $D$ is connected.

We calculate that $\mathrm{LHS} = 2n \cdot (n-1)$ grows quadratically and $\mathrm{RHS} = 2 ((2n+1)-1)$ grows linearly with respect to $n$.

For this particular $D$, the claim would work for $|A_D|$ instead of $|V_D|$ - this is why I asked about it in the comments.