{\mathtt{w}}^{*}(v) > {\mathtt{ub}}^{*}$ if and only if ${\mathtt{w}}'(u) + {\mathtt{w}}'(v) > {\mathtt{ub}}'$. Since ${\mathtt{w}}'(u) + {\mathtt{w}}'(v) \notin \{{\mathtt{lb}}', {\mathtt{ub}}'\}$ for all $(u,v)\in V^{2}$, it follows that ${\mathtt{w}}^{*}$, ${\mathtt{lb}}^{*}$, and ${\mathtt{ub}}^{*}$ define $G$, $\{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\}$, and ${\mathtt{w}}^{*}(u) + {\mathtt{w}}^{*}(v) \notin \{{\mathtt{lb}}^{*}, {\mathtt{ub}}^{*}\}$ for all $(u,v)\in V^{2}$.

The following lemma can be proved using a characterization of graphs of co-threshold dimension at most 2 [@RaschleS95]. Also, a proof of the same fact was given by Xiao and Nagamochi [@XiaoN18] using their characterization of double-threshold graphs. To make the discussion self-contained, we present a direct proof here.

\[lem:at-most-one-nonbipartite\] A double-threshold graph has at most one non-bipartite component.

Let $G$ be a double-threshold graph defined by ${\mathtt{w}}\colon V\to {\mathbb{R}}$ and ${\mathtt{lb}}, {\mathtt{ub}}\in {\mathbb{R}}$. It suffices to show that all cycles of odd lengths in $G$ belong to the same component.

Let $C$ and $C'$ be two induced cycles in $G$ that are vertex-disjoint and of odd lengths. Since $C$ is of odd length, we can find three vertices $a$, $b$, $c$ that consecutively appear in $C$ such that ${\mathtt{w}}(a) \le {\mathtt{w}}(b) \le {\mathtt{w}}(c)$. Similarly, we can find three consecutive vertices $x$, 