$y$, $z$ in $C'$ such that ${\mathtt{w}}(x) \le {\mathtt{w}}(y) \le {\mathtt{w}}(z)$. By symmetry, we may assume that ${\mathtt{w}}(b) \le {\mathtt{w}}(y)$. This implies that ${\mathtt{w}}(a) \le {\mathtt{w}}(y)$ and ${\mathtt{w}}(b) \le {\mathtt{w}}(z)$. Since $ab$ and $yz$ are edges, we have ${\mathtt{lb}}\le {\mathtt{w}}(a) + {\mathtt{w}}(b) \le {\mathtt{w}}(y) + {\mathtt{w}}(b) \le {\mathtt{w}}(y) + {\mathtt{w}}(z) \le {\mathtt{ub}}$. This implies that $by$ is also an edge, and thus $C$ and $C'$ belong to the same component.

We further observe that bipartite components can be considered separately. A bipartite graph is denoted by $(X, Y; E)$ when its vertex set is partitioned into two independent sets $X$ and $Y$ and its edge set is $E$.

\[lem:disjoint-bicomponent\] The disjoint union of a double-threshold graph and a bipartite double-threshold graph is a double-threshold graph.

Let $G = (V, E_{G})$ be a double-threshold graph defined by ${\mathtt{w}}_{G} \colon V \to {\mathbb{R}}$ and ${\mathtt{lb}}, {\mathtt{ub}}\in {\mathbb{R}}$. Let $H = (X,Y; E_{H})$ be a bipartite double-threshold graph. By Lemma \[lem:nice-representation\], we may assume that ${\mathtt{lb}}< {\mathtt{ub}}$ and $H$ is defined by the same ${\mathtt{lb}}$ and ${\mathtt{ub}}$ with some weight function ${\mathtt{w}}_{H} \colon X \cup Y \to {\mathbb{R}}$.

We set $\alpha \in {\mathbb{R}}_{\ge 0}$ large enough so that the following conditions hold: $$\begin{aligned}
  