&= \{uv \mid u,v \in V, \; {\mathtt{lb}}\le {\mathtt{w}}(u) + {\mathtt{w}}(v)\}, \\
  E_{2} &= \{uv \mid u,v \in V, \; -{\mathtt{ub}}\le -{\mathtt{w}}(u) -{\mathtt{w}}(v)\}.\end{aligned}$$ It holds that $(V, E_{1})$ and $(V, E_{2})$ are threshold graphs and that $E_{1} \cap E_{2} = E$.

The next lemma allows us to use any values as ${\mathtt{lb}}$ and ${\mathtt{ub}}$ for defining a double-threshold graph. It also says that we do not have to consider degenerated cases, where some vertices have the same weight or some weight sum equals to the lower or upper bound.

\[lem:nice-representation\] Let $G = (V,E)$ be a double-threshold graph defined by ${\mathtt{w}}\colon V \to {\mathbb{R}}$ and ${\mathtt{lb}}, {\mathtt{ub}}\in {\mathbb{R}}$. For every pair $({\mathtt{lb}}^{*}, {\mathtt{ub}}^{*}) \in {\mathbb{R}}^{2}$ with ${\mathtt{lb}}^{*} < {\mathtt{ub}}^{*}$, there exists ${\mathtt{w}}^{*} \colon V \to {\mathbb{R}}$ defining $G$ with ${\mathtt{lb}}^{*}$ and ${\mathtt{ub}}^{*}$ such that

1.  $\{v \mid {\mathtt{lb}}/2 \le {\mathtt{w}}(v) \le {\mathtt{ub}}/2\} = \{v \mid {\mathtt{lb}}^{*}/2 \le {\mathtt{w}}^{*}(v) \le {\mathtt{ub}}^{*}/2\}$,

2.  ${\mathtt{w}}^{*}(u) + {\mathtt{w}}^{*}(v) \notin \{{\mathtt{lb}}^{*}, {\mathtt{ub}}^{*}\}$ for all $(u,v) \in V^{2}$, and

3.  ${\mathtt{w}}^{*}(u) \ne {\mathtt{w}}^{*}(v)$ if $u \ne v$.

If $G$ has no edge, then the lemma trivially holds. Thus, we assume that $G$ has at least one edge. This implies that ${\mathtt{lb}}\le {\mathtt{ub}}$.

\[clm:nicer-rep1\] There exist ${\mathtt{lb}}', 