$x,y\in V$ we also have $G'_{x\to y}\in {\mathcal{G}}$. In addition suppose that $G$ satisfies $$d_2(G) = \max{\left\{d_2(G')\;:\;G'\in {\mathcal{G}}\right\}}.$$ Then $G$ is threshold.

Suppose $x,y\in V$ and $N_G[x]$ and $N_G[y]$ are incomparable. By hypothesis, $G_{x\to y}\in {\mathcal{G}}$ and by Lemma \[lem:allcompressed\] we know $d_2(G_{x\to y}) > d_2(G)$. This contradicts the assumption that $G$ attains the maximum value of $d_2$ in ${\mathcal{G}}$. Thus, $N_G[x] \subseteq N_G[y]$ or $N_G[y]\subseteq N_G[x]$ and so $G$ is threshold by Lemma \[thresholdnbhd\].

We will use the closely related topic of threshold bipartite graphs to prove Theorem \[bipartite\]. In [@OrangeBook] threshold bipartite graphs are defined with a similar vertex weighting.

\[thresholdbipartite\] A graph $G=(V,E)$ is said to be *threshold bipartite* if there exists a threshold $t$ and a function $w: V(G) \to {\mathbb{R}}$ such that $\abs{w(v)}<t$ for all $v\in V$ and distinct vertices $u$ and $v$ are adjacent if and only if $\abs{w(u)-w(v)}\geq t$.

Threshold bipartite graphs are called difference graphs in [@OrangeBook] and chain graphs in [@Yannakakis]. As with threshold graphs, there are many equivalent definition of threshold bipartite graphs. The following lemma describes the definition that will be most useful to us.

\[bipartiteinclusion\] A graph is threshold bipartite if and only if $G$ is bipartite and 