\mychapter{Cloning}

In this chapter, we define a second reduction operation called cloning.  Cloning will help us determine what types of vertices can be adjacent to vertices of degree $k-1$ in a minimal counterexample to the third statement of Theorem \ref{thm:main}.  It is crucial to understand the structure near these vertices if we are to succeed with a discharging argument, because vertices of degree $k-1$ are the vertices which need to be sent charge in order to complete the full proof of Theorem \ref{thm:main}.  Many results in this section are about structures that exist around vertices of \emph{low} degree, meaning vertices of degree $k-1$.
By examining graphs resulting from this cloning operation, we are able to identify the configurations which need to be accounted for by our discharging rules.

\begin{definition}
Let $G$ be a $k$-critical graph with $xy\in E(G)$ such that $\deg_G(x)=k-1$.  We define the operation of \emph{cloning $x$ with $y$} to mean constructing a new graph $G_{y\rightarrow x}$ such that $V(G_{y\rightarrow x})=(V(G)-\{y\})\cup\{\tilde{x}\}$ and $E(G_{y\rightarrow x})=E(G-\{y\})\cup\{\tilde{x}v\mid v\in N_G(x)\}\cup\{\tilde{x}x\}$.
\end{definition}

\section{Clusters}

We also use the notion of a cluster defined in \cite{KY2014}.  Recall that for a graph $G$ and vertex $x$, the closed neighborhood of $x$ is the set $N_G[x]=N_G(x)\cup\{x\}$.
\begin{definition}
A \emph{cluster} is a maximal set $R\subseteq V(G)$ such that for every $x\in R$, $\deg_G(x)=k-1$ and for every pair $x,y\in R$, $N_G[x]=N_G[y]$.
\end{definition}

A cluster, then, is a set of pairwise adjacent vertices of low degree.  
Further, if $x\in V(G)$ is in a cluster $C$ and $xy\in E(G)$ then when we clone $x$ with $y$, the new vertex $\tilde{x}$ is added to the cluster $C$.
Because large clusters will create areas in the graph that need quite a lot of charge, we want to bound the size of clusters in a minimal counterexample to the third statement of Theorem \ref{thm:main}.

\begin{proposition}\label{prp:ClusterBound}
Let $C$ be a cluster in a minimal counterexample $G$ to the third statement of Theorem \ref{thm:main}.  Then $|C|\leq k-3$.  Furthermore, if $C\subseteq S$ such that $G[S]=K_{k-1}$, then $|C|\leq\frac{k+1}{2}$.
\end{proposition}
\begin{proof}
Suppose that $G$ is a minimal counterexample to the third statement of Theorem \ref{thm:main} and that $C$ is a cluster of size $s$ in $G$.
Clearly $s<k$ because otherwise $G=K_k$, which cannot be a counterexample.
If $s=k-1$ then $C$ is an emerald of $G$.
If $s=k-2$, then we label the neighbors of $x$ outside of $C$ with $u$ and $v$.
Note that the graph $G[C\cup\{u,v\}]$ is a diamond of $G$.
Therefore, by Corollary \ref{cor:MinimalNoGems} we have $s\leq k-3$.

Suppose that $C$ is in a $K_{k-1}$ subgraph.
Label the vertices of the $K_{k-1}$ with $\{x_1,\ldots,x_{k-1}\}$, so that 
$x_i\in C$ for $1\leq i\leq s$.
For $i\leq s$, all $x_i$ share a common neighbor $y$ outside of the $K_{k-1}$.
If $s\geq\frac{k+2}{2}$ then this corresponds to at most $\frac{k-4}{2}$ edges that we can add between $y$ and $x_i$ for $i>s$ to obtain a $K_k$.
By Lemma \ref{lem:TightGeneralEdgeAddition}, this $\frac{k+2}{2}$-edge-addition is a contradiction.
\end{proof}


Notice that if we clone a degree $k-1$ vertex $x$ using a vertex $y$ with $\deg_G(y)>k-1$ then $G_{y\rightarrow x}$ is a smaller graph than $G$.  Further, if both $x$ and $y$ have degree $k-1$ in $G$, $x$ is in a cluster of size $s$ and $y$ is in a different cluster of size $t$ with $s\geq t$ then $G_{y\rightarrow x}$ is smaller than $G$.  The following lemma is true for any $k$-critical graph $G$, not just a minimal counterexample to Theorem \ref{thm:main}.

\begin{lemma}\label{lem:CloningNotColorable}
Given a $k$-critical graph $G$ if $xy\in E(G)$, $x$ is in a cluster of size $s$, $\deg_G(y)\leq k-2+s$, and $x$ and $y$ are not in a common cluster then $G_{y\rightarrow x}$ is not properly $(k-1)$-colorable.
\end{lemma}
\begin{proof}
Suppose that $G$ is a $k$-critical graph with $xy\in E(G)$ such that $x$ is in a cluster $C$ of size $s$ and $\deg_G(y)=k-2+s$.
Let $\phi$ be a proper $(k-1)$-coloring of $G_{y\rightarrow x}$.
Consider $\phi|_{V(G)-\{y\}}$ as a partial proper coloring of $G$.
We extend $\phi$ by coloring $y$ using a color distinct from its $k-2$ neighbors not in $C$.
Because $G$ is $k$-critical this is not a proper coloring; we may assume that $\phi(x)=\phi(y)$.
This is the only impediment to $\phi$ being a proper $(k-1)$-coloring of $G$.
However, we can now color $x$ with $\phi(\tilde{x})$ instead and we have properly $(k-1)$-colored $G$.
This contradiction completes the proof.
\end{proof}

We return to a minimal counterexample $G$ to the third statement of Theorem \ref{thm:main}.  
Suppose that $xy\in E(G)$ and that $\deg_G(x)=k-1$, $\deg_G(y)\leq k-2+s$, and $x$ and $y$ are not in a common cluster.
Now consider the graph $G_{y\rightarrow x}$.
By Lemma \ref{lem:CloningNotColorable}, $G_{y\rightarrow x}$ is not $(k-1)$-colorable.
Therefore, we let $H\subseteq G_{y\rightarrow x}$ be a $k$-critical subgraph.
The new vertex $\tilde{x}$ has degree $k-1$ in $H$ which, for $R=V(H)-\{\tilde{x}\}$, implies that
\[\rho_G(R)\le\rho(H)-(k-2)(k+1)-\epsilon+2(k-1)(k-1)+\delta,\]
which we write as
\begin{equation}\label{eq:cloned}
\rho_G(R)\leq\rho(H)+k^2-3k+4-\epsilon+\delta.
\end{equation}


\begin{lemma}\label{lem:CloningGivesGadget}
Suppose that $G$ is a minimal counterexample to the third statement of Theorem \ref{thm:main} and $xy\in E(G)$ such that 
\begin{enumerate}
\item $x$ is in a cluster $C_x$ of size $s$,
\item $\deg_G(y)\leq k-2+s$, and 
\item if $y$ is in a cluster $C_y$ then $C_y\neq C_x$ and $|C_y|=t\leq s$.
\end{enumerate}
Then for a $k$-critical subgraph $H\subseteq G_{y\rightarrow x}$ either $H$ is $k$-Ore or $H=G_{y\rightarrow x}$.
Moreover, $H=G_{y\rightarrow x}$ is only possible if $\deg_G(y)=k-1$.
\end{lemma}
\begin{proof}
Let $G$ be a minimal counterexample to the third statement of Theorem \ref{thm:main} and suppose that there is an $xy\in E(G)$ such that $x$ is in a cluster $C_x$ of size $s$ and $\deg_G(y)\leq k-2+s$.  Suppose further that if $y$ is in a cluster $C_y$ then $C_y\neq C_x$ and $|C_y|=t\leq s$.
We clone $x$ using $y$ to obtain the graph $G_{y\rightarrow x}$.
By Lemma \ref{lem:CloningNotColorable}, there exists a $k$-critical subgraph $H\subseteq G_{y\rightarrow x}$.
The conditions on cluster size ensure that $H\subseteq G_{y\rightarrow x}$ is smaller than $G$.
Suppose, for sake of contradiction, that $H$ is not $k$-Ore and $H\neq G_{y\rightarrow x}$.

Let $R=V(H)-\tilde{x}$.
Equation \ref{eq:cloned} gives a bound on $\rho_G(R)$ which we need to use.
Let $R'$ be a $W$-critical extension of $R$ in $G$.
By Lemma \ref{lem:CriticalExt} we get $\rho(G)\leq\rho_G(R')\leq\rho_G(R)+\rho(W)-\left(\rho(K_{|X|})+\delta T(K_{|X|})-\delta|X|\right)$.  
We will examine this potential more closely in cases based on the size of $X$.

Suppose first that $1<|X|<k-1$.  Then from Fact \ref{fct:CompletePotential} and Equation \ref{eq:cloned} it follows that 
\[\rho(G)\leq \rho(H)+\rho(W)-k^2+k+6-3\epsilon+3\delta.\]
Because $H\subseteq G_{y\rightarrow x}$ is smaller than $G$, is not a $k$-Ore graph, and $G$ is a minimal counterexample, this implies that $k^2-k-6+3\epsilon-3\delta<\rho(W)$.  This is a contradiction to Theorem \ref{thm:main}, since $W$ is smaller than $G$ and thus $\rho(W)\leq k^2-3k$.

Suppose instead that $|X|=k-1$.
Then Fact \ref{fct:CompletePotential} implies that
\begin{equation}\label{eq:CloningCorek-1}
\rho(G)\leq\rho(H)+\rho(W)-k^2+3k-k\epsilon+k\delta.\
\end{equation}
Again, $H\subseteq G_{y\rightarrow x}$ is smaller than $G$, is not a $k$-Ore graph, and $G$ is a minimal counterexample. Therefore this implies that
$k^2-3k+k\epsilon-k\delta<\rho(W)$.
This is a contradiction unless $W$ is $k$-Ore, so we may assume that $W$ is $k$-Ore.
%ACTUALLY, I THINK THIS IS ALWAYS A CONTRADICTION.  NO Kk-3 case??!!
Under this assumption, the inequality in Equation \ref{eq:CloningCorek-1} is tight in the sense that lowering the right hand side by $2(k-1)$ leads to a contradiction.
Thus, if the $W$-critical extension $R'$ is not spanning or is not complete, then the right hand side of Equation \ref{eq:CloningCorek-1} is lowered by at least $2(k-1)$ and we have a contradiction.

Suppose that $W$ is $K_k$, then because $R'$ is spanning, there is only one vertex in $V(G)-R$.  Therefore, $V(G)=R\cup\{y\}$ and $V(H)=R\cup\{\tilde{x}\}$ and it follows that $|V(G)|=|V(H)|$.
However, $H$ is smaller than $G$ and thus $\rho(H)\leq\rho(G)$.
Also, because their vertex sets overlap except at one vertex, $T(H)$ and $T(G)$ differ by at most 1.
Therefore, it is not possible for $G$ to have more edges than $H$, and we also have $|E(G)|=|E(H)|$.
If $\deg_G(y)>k-1$ then this contradicts the fact that $H$ is smaller than $G$.
If $\deg_G(y)=k-1$ then it follows that $H=G_{y\rightarrow x}$, which contradicts our assumption on $H$.

If $W$ is not $K_k$, then $X\subseteq V(W)$ is a $K_{k-1}$ subgraph and by Lemma \ref{lem:kOreAwayFromSet} there is an emerald or a diamond $D$ in $W$ disjoint from $X$.
If $D$ is a diamond then because $V(D)\subseteq V(W)-X\subseteq V(G)$ there is an edge-addition in $G$, which contradicts Lemma \ref{lem:MinimalNoEdgeAddition}.
If $D$ is an emerald, then $D$ is also a $K_{k-1}$ subgraph of $G$.
However, because the extension $R'$ is complete, each $x\in V(D)$ has at most one adjacency with each color class in $X$ and thus $\deg_G(x)=k-1$.
Therefore $D$ is an emerald of $G$, which contradicts Corollary \ref{cor:MinimalNoGems}.

Now we examine the final case; suppose that every $W$ critical extension has core size $|X|=1$.
With this assumption and Equation \ref{eq:cloned}, it follows that
\begin{equation}\label{eq:CloningCore1}
\rho_G(R')\leq\rho(H)+\rho(W)-2k+6-2\epsilon+2\delta.
\end{equation}
If $R'$ is not a spanning $W$-critical extension, then $R'$ must satisfy Corollary \ref{cor:ProperPotential}.
Therefore it follows that $\rho(G)+k^2-3k+2+\delta\leq \rho(H)+\rho(W)-2k+6-2\epsilon+2\delta$.
Because $H$ is smaller than $G$ and is not $k$-Ore, this implies that 
$k^2-k-4+2\epsilon-\delta<\rho(W)$, which is a contradiction.  Therefore $R'$ is spanning.  

We now check how incomplete this extension can be.  If $R'$ is $i$-incomplete then Equation \ref{eq:CloningCore1} becomes
\[\rho_G(R')\leq\rho(H)+\rho(W)-2k+6-2i(k-1)-2\epsilon+2\delta.\]
The left hand side is $\rho(G)$, since $R'$ is spanning. 
Thus, since $H$ is not $k$-Ore and is smaller than $G$, this yields
\begin{equation}\label{eq:CloningCore1Second}
0<\rho(W)-2k+6-2i(k-1)-2\epsilon+2\delta.
\end{equation}
We know that $\rho(W)\leq\rho(K_k)$ since it is also smaller than $G$, so if we assume that $i\geq\frac{k-3}{2}$ then we get 
$0<-k+3+(k-2)\epsilon.$
This is a contradiction, so we know that $R'$ is at most $\frac{k-4}{2}$-incomplete.

If every $W$-critical extension of $R$ is at most $\frac{k-6}{2}$-incomplete, then by Proposition \ref{prp:WheniCollapsible} $R$ is $\frac{k-6}{2}$-collapsible.
Then Proposition \ref{prp:iCollapsiblei1EdgeAddition} implies that $G$ admits a $\frac{k-4}{2}$-edge-addition, which contradicts Lemma \ref{lem:TightGeneralEdgeAddition}.
Therefore, we can pick a $W$-critical extension $R'$ so that the extension is either exactly $\frac{k-5}{2}$-incomplete or $\frac{k-4}{2}$-incomplete, depending on parity of $k$.

Suppose that $W$ is not $k$-Ore.  Then using the fact that $\rho(W)\leq k^2-3k-2(k-1)$ and $i\geq\frac{k-5}{2}$, Equation \ref{eq:CloningCore1Second} becomes
$0<k+1-2\epsilon+2\delta-2(k-1)$, which is a contradiction.
Therefore we may assume that $W$ is $k$-Ore.

By Lemma \ref{lem:kOreAwayFromVertex}, there exists a subgraph $D\subseteq W-\{X\}\subseteq G$ which is a diamond or emerald of $W$.
If $D$ is a diamond, then it admits a 1-edge-addition.  This is also a 1-edge-addition in $G$, which contradicts Lemma \ref{lem:MinimalNoEdgeAddition}.
Therefore, $D$ is an emerald of $W$. 
Because of the incompleteness of the extension, it is possible that $D$ is not an emerald in $G$.
However, $R'$ is at most $\frac{k-4}{2}$ incomplete, so there are at most $\frac{k-4}{2}$ vertices of $D$ that do not have degree $k-1$ in $G$.
If $u_1,u_2\in V(D)$ have degree $k-1$ in $G$ and are adjacent to $w_1,w_2\in V(G)-V(D)$ (respectively) with $w_1\neq w_2$, then $w_1w_2$ is a 1-edge-addition in $G$.
Thus, there exists a vertex $w\in V(G)-V(D)$ such that all $u\in V(D)$ with $\deg_G(u)=k-1$ are adjacent to $w$.  
But now $G[V(D)\cup\{w\}]$ is a $K_k$ missing at most $\frac{k-4}{2}$ edges.
This $\frac{k-4}{2}$-edge-addition in $G$ contradicts Lemma \ref{lem:TightGeneralEdgeAddition}.

Therefore, all cases lead to contradiction, and it must be that $H$ is $k$-Ore or $H=G_{y\rightarrow x}$.  Moreover, the only case (when $W=K_k$ and $|X|=k-1$) that contradicts the assumption that $H\neq G_{y\rightarrow x}$ required $\deg_G(y)=k-1$.
Further, if $H$ is $k$-Ore and $H=G_{y\rightarrow x}$ then $W=K_k$ and $|X|=k-1$.
Now if $\deg_G(y)>k-1$ then the right hand side of Equation \ref{eq:CloningCorek-1} is at least $2(k-1)$ smaller, which is a contradiction.
So it follows that $H=G_{y\rightarrow x}$ is only possible if $\deg_G(y)=k-1$.
\end{proof}
%that last stuff is confusing...





\section{Gadgets and $K_{k-3}$ subgraphs}
We now explore the structure of subgraphs of a minimal counterexample to the third statement of Theorem \ref{thm:main}.
\begin{definition}
A \emph{gadget}, $H^\circ$, is a graph obtained from a $k$-Ore graph $H$ by deleting a vertex $x$ of degree $k-1$ in a cluster of size at least 2.  For a graph $G$, a \emph{gadget of $G$} is a subgraph in $G$ that is a gadget.
\end{definition}

\begin{definition}
A \emph{key vertex} of a $k$-Ore graph $H$ is a vertex which is on the edge-side of every possible Ore composition that yields $H$.  We also define a key vertex of a gadget to be a vertex which is a key vertex of the corresponding $k$-Ore graph.
\end{definition}

Using this new language, we obtain the following corollary to Lemma \ref{lem:CloningGivesGadget} regarding adjacent vertices of degree $k-1$ which belong to different clusters.


\begin{corollary}\label{cor:CloningStructure}
Suppose that $G$ is a minimal counterexample to the third statement of Theorem \ref{thm:main} and $xy\in E(G)$ such that 
\begin{enumerate}
\item $x$ is in a cluster $C_x$ of size $s$,
\item $\deg_G(y)\leq k-2+s$, and 
\item if $y$ is in a cluster $C_y$ then $C_y\neq C_x$ and $|C_y|=t\leq s$.
\end{enumerate}
Then $x$ is a key vertex of a gadget of $G$ or $x$ is in a $K_{k-3}$ subgraph of $G$.
Moreover, if the latter is true then $\deg_G(y)=k-1$.
\end{corollary}

\begin{proof}
Let $G$ be a minimal counterexample to the third statement of Theorem \ref{thm:main} and suppose that there is an $xy\in E(G)$ such that $x$ is in a cluster $C_x$ of size $s$ and $\deg_G(y)\leq k-2+s$.  Suppose further that if $y$ is in a cluster $C_y$ then $C_y\neq C_x$ and $|C_y|=t\leq s$.
Then by Lemma \ref{lem:CloningGivesGadget}, there is a $k$-critical graph $H$ which is a subgraph of $G_{y\rightarrow x}$ and either $H$ is $k$-Ore or $H=G_{y\rightarrow x}$.
Note that if $H=G_{y\rightarrow x}$ then $\deg_G(y)=k-1$.

If $H$ is $k$-Ore, then $H^\circ=H-\{\tilde{x}\}$ is a gadget of $G$ which contains the vertex $x$.  
Suppose that $H=K_k$.  Then trivially every vertex of $H^\circ$ is a key vertex.
Suppose instead that $H$ is an Ore composition of two $k$-Ore graphs $H_1$ and $H_2$ with overlap vertices $\{a,b\}$.  
If $\tilde{x}\in V(H_2)$ then $ab$ is a $1$-edge-addition in $G$, which contradicts Lemma \ref{lem:MinimalNoEdgeAddition}.
Therefore $\tilde{x}$ must be on the edge-side of every Ore composition that yields $H$.
Because $\tilde{x}$ and $x$ have the same closed neighborhoods in $H$, this is also true of $x$.

If $H$ is not $k$-Ore, then $H=G_{y\rightarrow x}$. Because $\deg_G(x)=\deg_G(y)$, we know that there are the same number of edges in $H$ and $G$.  
But the hypothesis $s\geq t$ implies that $H$ is smaller than $G$ and so $H$ follows Theorem \ref{thm:main}.
Therefore $H$ must have lower potential than $G$.
Because they have the same number of edges, the potential can only have dropped because $T(H)>T(G)$.
This implies that $\tilde{x}$, and hence $x$, is in a $K_{k-2}$ subgraph of $H$ or is in a $K_{k-1}$ subgraph of $H$.
In either case, $x$ is in a $K_{k-3}$ subgraph of $G$.
\end{proof}


Using Corollary \ref{cor:CloningStructure}, we will define the various types of vertices of degree $k-1$ which can exist in $G$.  A vertex $u_1\in V(G)$ of degree $k-1$ could be in a $K_{k-3}$ subgraph or could be a key vertex of a gadget.  It is possible that such a vertex is not found via Corollary \ref{cor:CloningStructure} (meaning there is no adjacent cluster to $u_1$).  We call these vertices \emph{structure-vertices}.
A vertex $u_2$ could belong to a cluster $C_{u_2}$ which is adjacent to no other clusters.  
If such a vertex $u_2$ is a key vertex of a gadget or is in a $K_{k-3}$ subgraph, then we will group with with the other structure-vertices.
If such a vertex $u_2$ is not a structure-vertex, then we call it a \emph{lone-vertex}.
If a vertex $u_3$ of degree $k-1$ has an adjacent cluster $C_v$ but is not a structure-vertex, then by Corollary \ref{cor:CloningStructure} it follows that $|C_{u_3}|<|C_v|$ (equality implies that $u_3$ is a structure-vertex) and that $C_v$ contains key vertices of a gadget or is in a $K_{k-3}$ subgraph.  We say that such a vertex $u_3$ is a \emph{near-vertex}.
In this way, we partition all vertices of degree $k-1$ in $G$ into these three disjoint categories: structure-vertices, lone-vertices, and near-vertices.

\begin{proposition}\label{prp:OnlyOneNearNeighbor}
If $x$ is a structure-vertex in a minimal counterexample to the third statement of Theorem \ref{thm:main}, then $x$ cannot be adjacent to two near-vertices $y,z$, each belonging to a different cluster.
\end{proposition}
\begin{proof}
Let $G$ be a minimal counterexample to the third statement of Theorem \ref{thm:main} and suppose that $x$ is a structure vertex with two near-vertex neighbors $y,z$ such that $y$ and $z$ belong to different clusters.

If $yz\in E(G)$ then, without loss of generality, we may assume that $G_{y\rightarrow z}$ is smaller than $G$.
By Corollary \ref{cor:CloningStructure}, $z$ is a structure-vertex of $G$ and cannot be a near-vertex.
This is a contradiction.

If $yz\notin E(G)$ then, in the graph $G_{x\rightarrow z}$ the degree of $y$ is $k-2$.  Therefore, by Lemma \ref{lem:CloningNotColorable}, there is a $k$-critical subgraph $H\subseteq G_{x\rightarrow z}$.
Because $y\notin V(H)$, we know that $H$ is smaller than $G$ and therefore, by the proof of Corollary \ref{cor:CloningStructure}, $z$ is a key vertex of a gadget.
This contradicts the fact that $z$ is a near-vertex.
\end{proof}


\section{Bounds on degrees of neighbors\\ of structure-vertices}

By Proposition \ref{prp:ReducedOre}, every $k$-Ore graph $H$ can be reduced to a $K_k$ where some number of edges of the $K_k$ are replaced by split-side $k$-Ore graphs in a composition operation when constructing $H$.  We call such an edge an \emph{edge-replacement}.  Recall that each edge-replacement $uv$ corresponds to a subgraph $D\subseteq G$ where, for any proper $(k-1)$-coloring of $D$, $u$ and $v$ must receive different colors.
If $x$ is a key vertex in $H$, then $x$ must be a vertex of the $K_k$.
Similarly, a gadget $H^\circ$ can be reduced to a $K_{k-1}$ with edge-replacements. A key vertex $x$ of $H^\circ$ will always be a vertex of this $K_{k-1}$, and if $\deg_{H^\circ}(x)=k-2$ then the neighbors of $x$ in $H^\circ$ are also key vertices of $H$.
This may not be immediately clear, but is shown in the proof of the following lemma.


\begin{lemma}\label{lem:DifferentKeyVertex}
Let $x$ be a key vertex of a gadget $H^\circ$ of a minimal counterexample $G$ to the third statement of Theorem \ref{thm:main}, and let $\deg_G(x)=k-1$.  If $y$ is a different key vertex of $H^\circ$ then either $N_G[x]\subseteq N_G[y]$ or $\deg_G(y)\geq 3(k-3)/2+1$.
%!!!!
\end{lemma}
\begin{proof}
Let $G$ be a minimal counterexample to the third statement of Theorem \ref{thm:main} and suppose that $H^\circ$ is a gadget of $G$ with key vertices $x,y$ where $\deg_G(x)=k-1$.
If $N_G[x]\subseteq N_G[y]$, then we are done so we may assume that $N_G[x]$ is not a subset of $N_G[y]$.
We define $H'$ to be a reduction of $H^\circ$ to a $K_{k-1}$ graph where some edges are edge-replacements; by definition, $x$ and $y$ are in $V(H')$.

Suppose that there is an edge $xu\in E(H')$ which is an edge-replacement that corresponds to $D\subseteq G$.
The graph $D$ is $(k-1)$-colorable but $x$ and $u$ must receive different colors.
%!!! I'd like a reference
Thus, in any proper $(k-1)$-coloring $\phi$ of $D$, the color $\phi(u)$ must be given to a vertex in $N_D(x)$.
But then we can add to $D$ a set of edges $S$ from $u$ to each vertex in $N_D(x)$ and get a $k$-critical subgraph in $D+S$.
By Lemma \ref{lem:TightGeneralEdgeAddition}, it follows that $|N_D(x)|\geq\frac{k-3}{2}$.
Therefore, because $\deg_G(x)=k-1$, the vertex $x$ can not be incident with any edge-replacements in $H'$.

From this, it follows that $xy\in E(G)$.  Also, $\deg_{H^\circ}(x)=k-2$ and $x$ must have one neighbor $w$ in $V(G)-V(H^\circ)$.
By Lemma \ref{lem:NeighborsDiffer} it follows that
\[\deg_G(y)\geq|N_G(x)\cap N_G(y)|+1+\frac{k-3}{2}=3(k-1)/2+1.\]
Suppose that $y$ is not incident with any edge-replacement in $H'$.
Then $V(H')-\{x,y\}=N_G(x)\cap N_G(y)$ and we get $\deg_G(y)\geq 3(k-1)/2+1$.
Suppose that $y$ is incident with an edge-replacement $yu$ in $H'$ that corresponds to a subgraph $C\subseteq G$.
As above, we can show that $|N_C(y)|\geq\frac{k-3}{2}$.
Therefore, for each $u\in V(H')-\{x,y\}$ that is not in $N_G(x)\cap N_G(y)$, we get a contribution of at least $\frac{k-3}{2}$ to the degree of $y$ in $G$.
We have, in fact, proven a slightly stronger statement than Lemma \ref{lem:DifferentKeyVertex}.
Namely, that if $N_G[x]$ is not a subset of $N_G[y]$ then $\deg_G(y)\geq ((k-3-i)+i\frac{k-3}{2})+1+\frac{k-3}{2}$, where $i$ is the number of edge-replacements of $H'$ incident to $y$.
\end{proof}



\begin{lemma}\label{lem:BoundOnKeyVertex}
Let $x$ be a key vertex in a gadget of $G$, where $G$ is a minimal counterexample to the third statement of Theorem \ref{thm:main} and $\deg_G(x)=k-1$.
Then $x$ has at least $\frac{k-3}{2}$ neighbors of degree at least $3(k-3)/2+1$.
\end{lemma}

\begin{proof}
Let $G$ be a minimal counterexample to the third statement of Theorem \ref{thm:main} such that $H^\circ$ is a gadget of $G$.  Suppose that $x$ is a key vertex of $H^\circ$ and that $\deg_G(x)=k-1$.
We define $H'$ to be a reduction of $H^\circ$ to a $K_{k-1}$ graph where some edges could be edge-replacements.
By definition of a key vertex, $x\in V(H')$ and the same argument as in the proof of Lemma \ref{lem:DifferentKeyVertex} shows that $x$ is not adjacent to any edge-replacements and $x$ has exactly one neighbor $w$ in $V(G)-V(H^\circ)$.
We partition $V(H')$ into sets $A,B$ where $A:=\{u\in V(H')\mid uw\in E(G)\}$ and $B:=\{u\in V(H')\mid uw\notin E(G)\}$.
By Lemma \ref{lem:DifferentKeyVertex}, each vertex $b\in B$ has $\deg_G(b)\geq3(k-1)/2+1$.

We can add to $G$ a set $S$ of $|B|$ edges from $w$ to each vertex $b\in B$.  
Because each vertex in $A\cup B\cup \{w\}$ needs a unique color, either this is a $|B|$-edge-addition or $V(G)=V(H^\circ)\cup\{w\}$.
In the first case, by Lemma \ref{lem:TightGeneralEdgeAddition}, it follows that $|B|>\frac{k-4}{2}$.
We show now that the second case is impossible.

Suppose that $V(G)=V(H^\circ)\cup\{w\}$.  
Then $H$ is a $k$-Ore graph with vertex set $V(H^\circ)\cup\{\tilde{x}\}$ and $\deg_H(\tilde{x})=k-1$.
The potential of $H$ is at most $\rho(H)\leq k(k-3)+k\epsilon-2\delta$.
Deleting the vertex $\tilde{x}$ and adding $w$ (with its adjacencies in $G$) gives us the graph $G$.
This operation affects only one vertex so $|T(H)-T(G)|\leq1$.
If $\deg_G(w)>k-1$ then $\rho(G)\leq \rho(H)-2(k-1)+\delta\leq k(k-3)-2(k-1)+k\epsilon-\delta$ which is a contradiction.

Therefore it follows that $\deg_G(w)=k-1$.
But now in any proper $(k-1)$-coloring $\phi$ of $G-\{w\}$, the subset $N_G(w)$ must have exactly one vertex of each color.
There exists at least one edge-replacement $uv\in E(H')$, otherwise $G=K_k$ which is a contradiction.
Let $D\subseteq G$ be the corresponding subgraph.
By Lemma \ref{lem:MinimalNo2Cut}, there cannot be a 2-cut in $G$ so there must be an edge from $w$ to some vertex $z\in V(D)-\{u,v\}$.
We may assume that $\phi$ colors $D$ such that $\phi(z)$ is different from $\phi(u)$ and $\phi(v)$, because otherwise $\{zu,zv\}$ is a 2-edge-addition which is a contradiction for $k\geq8$.
However, because $k-1\geq4$ we can switch the color class $\phi(z)$ so that $|\phi(N_G(w))|=k-2$.
This allows us to properly $(k-1)$-color $G$, which is a contradiction.
\end{proof}

\begin{lemma}\label{lem:BoundOnKk-3}
If $x$ is in a $K_{k-3}$ subgraph of $G$, where $G$ is a minimal counterexample to the third statement of Theorem \ref{thm:main}, and $\deg_G(x)=k-1$ then
$x$ has at least $(k-9)/6$ neighbors of degree at least $3(k-3)/2-1$.
\end{lemma}
\begin{proof}
Let $G$ be a minimal counterexample to the third statement of Theorem \ref{thm:main} such that $x\in V(G)$ is in a $K_{k-3}$ subgraph $D\subseteq G$ and $\deg_G(x)=k-1$.
The vertex $x$ has three neighbors $w_1,w_2,w_3\in V(G)-V(D)$.
We partition $V(D)$ into sets $A,B$ where $A:=\{u\in V(D)\mid uw_i\in E(G)\textrm{ for } 1\leq i\leq3\}$ and 
$B:=\{u\in V(D)\mid uw_i\notin E(G)\textrm{ for some }1\leq i\leq3\}$.

We can add to $G$ the edges $\{w_1w_2, w_1w_3, w_2w_3\}$ and $w_ib$ for $1\leq i\leq3$ and $b\in B$.
Adding this set $S$ of $3+3|B|$ edges gives a $K_k$ subgraph so is a $(3+3|B|)$-edge-addition.
By Lemma \ref{lem:TightGeneralEdgeAddition} it follows that $|B|\geq\frac{k-9}{2}$.

For $b\in B$, we know that $N_G[x]$ is not a subset of $N_G[b]$.
Also, $x$ and $b$ are each adjacent to the $k-5$ other vertices in $V(D)$.
Therefore by Lemma \ref{lem:NeighborsDiffer}, $b$ has degree at least $(k-5)+1+\frac{k-3}{2}=3(k-3)/2-1$.
\end{proof}


\begin{lemma}\label{lem:near-verticesKk-3}
If $x$ is in a $K_{k-3}$ subgraph $D\subseteq G$, where $G$ is a minimal counterexample to the third statement of Theorem \ref{thm:main}, $\deg_G(x)=k-1$, and $x$ has a neighbor $y\in V(G)-V(D)$ which is in a different cluster, then $x$ has at least $(k-7)/2$ neighbors of degree at least $3(k-3)/2-1$.
\end{lemma}
\begin{proof}
Let $G$ be a minimal counterexample to the third statement of Theorem \ref{thm:main} such that $x\in V(G)$ is in a $K_{k-3}$ subgraph $D\subseteq G$, $x$ has a neighbor $y\in V(G)-V(D)$, and both $x$ and $y$ have degree $k-1$ in $G$.
Further, $x$ and $y$ are in different clusters.
We partition $V(D)-\{x\}$ into sets $A,B$ where $A:=\{u\in V(D)-\{x\}\mid uy\in E(G)\}$ and $B:=\{u\in V(D)-\{x\}\mid uy\notin E(G)\}$.

By Lemma \ref{lem:NeighborsDiffer}, $x$ and $y$ cannot have too many neighbors in common because $\deg_G(y)=k-1$.
We get that $k-1=\deg_G(y)\geq|A|+1+\frac{k-3}{2}$, from which it follows that $|A|\leq\frac{k-1}{2}$.
But $V(D)=A\cup B\cup\{x\}$ so this implies that $|B|\geq\frac{k-7}{2}$.

Similar to Lemma \ref{lem:BoundOnKk-3}, one can show using Lemma \ref{lem:NeighborsDiffer} that $b\in B$ has degree at least $3(k-3)/2-1$.
\end{proof}



%\section{make sure these find places in final}
%
%
%\begin{corollary}
%If $u$ is a key vertex of dgree $(k-1)$ in $G$ and has a nbr $v$ of degree $k-1$ in $G$, then they are in the same cluster in $G$.
%\end{corollary}
%\begin{proof}
%To show this we only need to show that the out-neighbor is common.
%\end{proof}

