 conditions (i),(ii) and (iii). Since the $r_i$ satisfy (i),(ii),(iii), we get $v(P)\leq 1+\sum_j (\delta/q_j+(\alpha-1))$. We are left to prove (v), so let us suppose that it does not hold. There are two cases to consider.
\smallskip
	
	\emph{Case 1.} If there exists some $i$ with $q_i=2$, then there is a $j$ such that $q_j\not \in \{2,R\}$ and by (iii) we have $q_j\geq k$. Hence, $\delta/q_j-\delta/(q_j+1)<\eta/2$. After relabelling, we may assume that $j=w-1,i=w$. Now set $w'=w-1$, $q'_h=q_h$ for all $h\leq w-2$ and $q'_{w-1}=q_{w-1}+1$. Then $q'_1,...,q'_{w'}$ satisfy (i),(ii),(iii) and 
	\[1+\sum_{h\leq w} (\delta/q_h+(\alpha-1))<1+\sum_{h\leq w'} (\delta/q'_h+(\alpha-1)),\] 
which is a contradiction.
\smallskip	

	\emph{Case 2.} If there is no $i$ with $q_i=2$, then since (v) is assumed to fail, there must exist $i\neq j$ with $2<q_i\leq q_j<R$. Moreover, we may assume that $q_i$ is minimal among all $q_h$s. Without loss of generality, $i=w-1,j=w$. Now define $q'_h=q_h$ for all $h\leq w-2$, $q'_{w-1}=q_{w-1}-1$ and $q'_w=q_w+1$. Then $q'_1,...,q'_{w}$ satisfy (i),(ii),(iii) and 
	\[1+\sum_{h\leq w} (\delta/q_h+(\alpha-1))<1+\sum_{h\leq w} (\delta/q'_h+(\alpha-1)),\] 
which is a contradiction.
\medskip

	This completes the proof of Claim 1.
\medskip
	
\noindent \emph{Claim 2.} If $q_1,...,q_w$ satisfy the conditions (i),(ii),(v) in Claim 1, then 
\[1+\sum_{h\leq w} (\delta/q_h+(\alpha-1))< 2\delta/t.\]
	
\noindent \emph{Proof of Claim 2.} For $t\leq 13$, this is a straightforward check, which we performed using a computer program, since it would have taken inordinately long to do it by hand. (The code, written in Matlab, can be found at the end of the appendix.) So we shall assume that $t\geq 14$. Then $3R\geq 3\cdot\frac{t-2}{2}>t+2$, so there are at most two $q_j$s with $q_j=R$. Using (v), this leaves the following cases.
\smallskip
	
	Case 1: $q_j=2$ for all $j$
	
	Case 2: $q_1=R$	and $q_j=2$ for all $j\geq 2$
	
	Case 3a: $q_1=q_2=R=\frac{t-2}{2}$ and $q_3=q_4=q_5=2$ ($w=5$)
	
	Case 3b: $q_1=q_2=R=\frac{t-1}{2}$ and $q_3=q_4=2$	($w=4$)
	
	Case 4a: $q_1=q_2=R=\frac{t-2}{2},q_3=4$ ($w=3$)
	
	Case 4b: $q_1=q_2=R=\frac{t-1}{2},q_3=3$ ($w=3$)
	
\medskip
	
         By Lemmas \ref{app1} and \ref{app2} (d) we have $$(l-1)(\delta/2+(\alpha-1))<(\delta/l+(\alpha-1))$$ when $l=\frac{t-1}{2}$. Moreover, we have the inequality 
         \[\big(\delta/\Big(\frac{t-2}{2}\Big)+(\alpha-1)\big)+\frac{1}{2}\big(\delta/2+(\alpha-1)\big)<\big(\delta/\Big(\frac{t-1}{2}\Big)+(\alpha-1)\big),\] 
since this is equivalent to $\frac{2\delta}{(t-1)(t-2)}<\eta/4$, which holds because $(t-1)\eta\geq 2\delta$ and $t-2>4$. It is not hard to see that these two observations allow us to deduce all Cases 1-3 from Case 3b. To prove Case 3b, we need the inequality 
\[1+2(\delta/(\frac{t-1}{2})+(\alpha-1))-\eta< 2\delta/t,\] which is given in Lemma \ref{app2} (f).
	
	Clearly, Case 4a follows from Case 4b. To prove Case 4b, we need 
	\[1+2(\delta/(\frac{t-1}{2})+(\alpha-1))+(\delta/3+(\alpha-1))< 2\delta/t.\] 
Using $\alpha<1/2$ and $\delta<1$, it suffices to prove that $4/(t-1)-2/t\leq 1/6$, which holds for $t\geq 14$.	
\medskip

This completes the proof of Claim 2, and the two claims imply the lemma.
\end{proof2}

\begin{lemma} \label{contains}
	Suppose that $Q$ is a scheme such that its $v(Q)$ is as large as possible and such that the largest block $D$ of $Q$ has size at least $t/2$. Then $D$ has size $s$.
\end{lemma}

\begin{proof2}
	Suppose not. Pick a node $P$ with $P\not \in D$. Let $D$ have size $k\geq t/2$. Suppose that $P$ is contained in exactly $r$ large blocks. Define a scheme $Q'$ as follows. $Q'$ has the same blocks as $Q$ except that $P$ is removed from all large blocks and added to $D$. The missing edges are now provided by distinct colours.
	
	We now compare the values $v(Q)$ and $v(Q')$. The node $P$ is in only one large block in $Q'$ while it is in $r$ large blocks in $Q$. The number of small blocks containing $P$ is precisely $t-k-1$ in $Q'$ while it is at least $k-r$ in $Q$. That is because any large block containing $P$ contains at most one element of $D$. So 
	\begin{align*}v(Q')-v(Q)&\geq (r-1)(1-\alpha)+((t-k-1)-(k-r))(\delta+2(\alpha-1))\\
	&=(r-1)(1-\alpha)-(t-2k+(r-1))\eta\geq (r-1)(1-\alpha-\eta).\\
	\end{align*} 
But $1-\alpha-\eta=\delta-(1-\alpha)=1/2+(2s-1)\epsilon-(1/2+\epsilon)>0$. This contradicts the maximality of $v'(Q)$ if $r\geq 2$.
	
	If $r=1$, then let the unique large block containing $P$ have size $l$. By assumption, $l\leq k$. Hence,  
	\[v(Q')-v(Q)=((t-k-1)-(t-l))(\delta+2(\alpha-1))=(k+1-l)\eta>0,\] 
a contradiction.
	
	If $r=0$, then 
	\[v(Q')-v(Q)=-(1-\alpha)-k(\delta+2(\alpha-1))=k\eta-(1-\alpha)\geq \frac{t}{2}\eta-(1-\alpha).\] 
But by Lemma \ref{app2} (d), this is at least $\delta-(1-\alpha)>0$. This is a contradiction and the lemma is proved.
\end{proof2}

\vspace{2mm}

We are ready to complete the proof of Lemma \ref{negscheme}.

\begin{proof}[\textnormal{\textbf{Proof of Lemma \ref{negscheme}.}}]
	We may assume that $v(Q)$ is maximal possible among all schemes $Q$. If $Q$ has a block of size $s