& \text{otherwise};
\end{cases}\\
\gamma &=&
\begin{cases}
\max \{ {\mathtt{w}}'(v) \mid {\mathtt{w}}'(v) < {\mathtt{w}}'(z) \} & \text{if there exists } v \text{ such that } {\mathtt{w}}'(v) < {\mathtt{w}}'(z),\\
-\infty & \text{otherwise}.
\end{cases}\end{aligned}$$ Let $$\varepsilon = \min\{{\mathtt{w}}'(z) + \alpha - {\mathtt{lb}}', {\mathtt{w}}'(z) + \beta - {\mathtt{ub}}', {\mathtt{w}}'(z) - \gamma, 
    |{\mathtt{w}}'(z) - {\mathtt{lb}}'/2|, |{\mathtt{w}}'(z) - {\mathtt{ub}}'/2|\}.$$ Note that $\varepsilon$ is positive and not infinitely large. By decreasing the weight of $z$ by $\varepsilon/2$, we define ${\mathtt{w}}''$. That is, ${\mathtt{w}}''(z) = {\mathtt{w}}'(z) - \varepsilon/2$ and ${\mathtt{w}}''(v) = {\mathtt{w}}'(v)$ for all other $v \ne z$.

Observe that $z$ has a unique weight under ${\mathtt{w}}''$ because $z$ is the only vertex of weight in the interval $(\gamma, {\mathtt{w}}'(z))$. Since all vertices other than $z$ have the same weight in ${\mathtt{w}}'$ and ${\mathtt{w}}''$, the number of unique-weight vertices under ${\mathtt{w}}''$ is larger than the one under ${\mathtt{w}}'$.

Next we show that ${\mathtt{w}}''(z) + {\mathtt{w}}''(v) \notin \{{\mathtt{lb}}',{\mathtt{ub}}'\}$ for all $v \in V$ and that ${\mathtt{w}}''$, ${\mathtt{lb}}'$, and ${\mathtt{ub}}'$ define $G$. Let $v \in V$. (Note that $v$ may be $z$.) By the assumption on ${\mathtt{w}}'$, we have ${\mathtt{w}}'(z) + {\mathtt{w}}'(v) \notin \{{\mathtt{lb}}', {\mathtt{ub}}'\}$. If ${\mathtt{w}}'(z) + {\mathtt{w}}'(v) < {\mathtt{lb}}'$, then ${\mathtt{w}}''(z) + {\mathtt{w}}''(v) < {\mathtt{lb}}'$ holds as ${\mathtt{w}}''(z) 