\mychapter{Potential and critical extensions}


\section{Potential}

We now recall the definition of the potential of a graph.
\begin{definition}
A graph $G$ has \emph{potential} 
\[\rho(G)=\left((k-2)(k+1)+\epsilon\right)|V(G)|-2(k-1)|E(G)|-\delta T(G).\]
\end{definition}

We can also define this function on vertex subsets $R$ of a graph $G$.  If $R\subseteq V(G)$, then let
\[\rho_G(R)=\left((k-2)(k+1)+\epsilon\right)|R|-2(k-1)|E(G[R])|-\delta T(G[R])\]
where we reacall that $G[R]$ is the induced subgraph of $G$ with vertex set $R$.  

Below, we begin the list of complete subgraphs of a $k$-critical graph for a fixed $k$, ordered from smallest potential to largest potential.
The complete subgraphs not listed all have larger potential than these four.

\begin{fact}\label{fct:CompletePotential}
\quad
\begin{enumerate}
\item $\rho(K_1)=k^2-k-2+\epsilon$.
\item $\rho(K_{k-1})=2k^2-6k+4+(k-1)\epsilon-2\delta$.
\item $\rho(K_2)=2k^2-4k-2+2\epsilon$.
\item $\rho(K_{k-2})=3k^2-11k+10+(k-2)\epsilon-\delta$.
\end{enumerate}
\end{fact}

To prove Theorem \ref{thm:main}, our strategy is to look at a minimal counterexample and use proof by contradiction.  Therefore, we now need to precisely define what makes a graph minimal.  Let $G$ and $H$ be two graphs.  
\begin{definition}
The graph $H$ is \emph{smaller} than $G$ if either $|E(G)|>|E(H)|$, or $|E(G)|=|E(H)|$ and $G$ has fewer pairs of vertices with the same closed neighborhood.
\end{definition}
\begin{definition}
A graph $G$ is \emph{good} if it is $k$-critical and every smaller $k$-critical graph satisfies Theorem \ref{thm:main}.
\end{definition}
Therefore, when we say that $G$ is a minimal counterexample to the third statement of Theorem \ref{thm:main}, we mean that it is a good graph which is not $k$-Ore and does not satisfy Theorem \ref{thm:main}.

\section{Critical extensions}

If $R$ is a proper subset of a $k$-critical graph $G$, then we can use the criticality of $G$ to define an extension of $R$.
First, note that if $R\subsetneq V(G)$, then we can $(k-1)$-color $G[R]$ with some proper coloring $\phi:R\rightarrow[k-1]$.
We define the graph $G_{R,\phi}$ to be the graph obtained from $G$ by identifying all vertices in $\phi^{-1}(i)$ to a single vertex $x_i$ for $1\leq i\leq k-1$,
adding the edge $x_ix_j$ for $1\leq i<j\leq k-1$, and then replacing any multiedges with single edges.  Note that we don't remove adjacencies in $G$, so that if $u\in R$, $v\in V(G)-R$, and $uv\in E(G)$ then $vx_{\phi(u)}\in E(G_{R,\phi})$.

The following lemma is proved in \cite{KY2014}, we include a proof for completeness.

\begin{lemma}\label{lem:GRphi}
If $G$ is a $k$-critical graph with $R\subsetneq V(G)$. Then $G_{R,\phi}$ is not $(k-1)$-colorable.
\end{lemma}
\begin{proof}
	Suppose the result fails to hold. Let $G$ be a $k$-critical graph with $R\subsetneq V(G)$ and let $\phi:R\rightarrow[k-1]$ be a proper $(k-1)$-coloring of $G[R]$.  By assumption, there is a proper $(k-1)$-coloring $\psi$ of $G_{R,\phi}$.  
Recall that $V(G_{R,\phi})=(V(G)-R)\cup\{x_1,\ldots,x_{k-1}\}$ and that $G_{R,\phi}[\{x_1,\ldots,x_{k-1}\}]$ is a $K_{k-1}$.
	We change the labels of $\psi$ so that $\psi(x_i)=i$ for each vertex $x_i\in V(G_{R,\phi})$.  However, $\psi|_{V(G)-R}\cup\phi|_R$ is now a proper $(k-1)$-coloring of $G$, which is a contradiction.  Therefore, the result must hold.
\end{proof}

By Lemma \ref{lem:GRphi}, we know that there is a $k$-critical subgraph $W\subseteq G_{R,\phi}$.
Because $G$ is $k$-critical, $W$ must contain at least one vertex in $\{x_1,\ldots,x_n\}$.
We let $X:=V(W)\cap\{x_1,\ldots,x_n\}$ and $R':=(R\cup V(W))-X$.
Note that $R\subsetneq R'\subseteq V(G)$.
We say that $R'$ is a \emph{$W$-critical extension} of $R$ and that $X$ is the \emph{core} of the extension.


\begin{lemma}\label{lem:CriticalExt}
If $R'$ is a $W$-critical extension of $R\subsetneq V(G)$ with core $X$, then
\begin{equation}\label{eq:CritExtBasic}
\rho_G(R')\leq \rho_G(R)+\rho(W)-\rho(K_{|X|})-\delta T(K_{|X|})+\delta|X|.
\end{equation}
\end{lemma}
\begin{proof}
The three elements of a graph that contribute to potential are vertices, edges, and the number of $K_{k-1}$ and $K_{k-2}$ subgraphs.
Because $R'=R\cup V(W)-X$, each side of Equation \ref{eq:CritExtBasic} counts the same number of vertices.
For the edges, each side of Equation \ref{eq:CritExtBasic} counts some edges that the other does not.  Note that $\rho_G(R')$ counts edges in $G$ from $R$ to $V(W)-X$.  
The right-hand side counts edges in $G_{R,\phi}$ from $X$ to $V(W)-X$.  All other edges (those inside $G[R]$ and those inside $W-\{X\}$) are accounted for by both sides of Equation \ref{eq:CritExtBasic}.
However each edge from $R$ to $V(W)-X$ in $G$ maps to an edge from $X$ to $V(W)-X$.
Therefore we have the desired inequality with respect to the edge-contribution to potential.

Finally we look at the $K_{k-1}$ and $K_{k-2}$ subgraphs.  Now $T(G[R'])$ must be at least the sum of $T(G[R])$ and $T(W-\{X\})$.
Also, $T(W-\{X\})$ must be at least $T(W)-|X|$ because each $x_i\in X$ could be in, at worst, one subgraph counted by $T(W)$.
Therefore, we get the desired inequality in Equation \ref{eq:CritExtBasic}.
\end{proof}

\begin{corollary}\label{cor:ExtensionDrop}
For good graphs $G$ with $R\subsetneq V(G)$, $\rho_G(R')\leq\rho_G(R)-2(k-1)-\delta$.
\end{corollary}
\begin{proof}
By Fact \ref{fct:CompletePotential}, we can see that 
$\rho(K_{|X|})+\delta T(K_{|X|})-\delta|X|$ is minimized when $|X|=1$.
Therefore, Lemma \ref{lem:CriticalExt} becomes
\begin{equation}\label{eq:ExtensionPotential}
\rho_G(R')\leq\rho_G(R)+\rho(W)-(k^2-k-2+\epsilon-\delta).
\end{equation}
If $W$ is $K_k$, then because $T(W)=T(W-\{x\})$ for $x\in X$ we can ignore the $+\delta$ in Equation \ref{eq:ExtensionPotential}.
Therefore for $W=K_k$ it follows that
\[\rho_G(R')\leq \rho_G(R)+(k^2-3k+k\epsilon-2\delta)-(k^2-k-2+\epsilon)\]
\[=\rho_G(R)-2(k-1)+(k-1)\epsilon-2\delta.\]

If $W$ is $k$-Ore and $W\neq K_k$ then it follows from Theorem \ref{thm:main} that
\[\rho_G(R')\leq \rho(G)+(k(k-3)+|V(G)|\epsilon-\left(2+\frac{|V(G)|-1}{k-1}\right)\delta)-(k^2-k-2+\epsilon-\delta).\]
Because $\delta\geq(k-1)\epsilon$, this implies that $\rho_G(R')\leq\rho_G(R)-2(k-1)-\delta$.

Finally, if $W$ is not $k$-Ore, then $\rho(W)\leq k(k-3)-2(k-1)$ because $G$ is a good graph.  Therefore we get
$\rho_G(R')\leq\rho_G(R)-4(k-1)-\epsilon$ and because $-2(k-1)-\epsilon\leq \delta$ we have proven the corollary.
\end{proof}

Corollary \ref{cor:ExtensionDrop} implies that in a minimal counterexample $G$ every proper subgraph $G[R]\subsetneq G$ has potential that is higher than $\rho(G)$ because we can continue making critical extensions, lowering the potential and growing the subset until we reach an extension which is all of $V(G)$.  Therefore $\rho(G)=\min\{\rho_G(R)\mid R\subseteq V(G)\}$, and we are able to use $\rho$ as a global parameter for discharging.

Suppose that $R'$ is a $W$-critical extension of $R\subsetneq V(G)$ with core $X$.  
We define $|X|$ to be the \emph{core size} of the $W$-critical extension.
If $R'=V(G)$ then we say that $R'$ is a \emph{spanning} critical extension.
Note that if $R'\neq V(G)$ then $G[R']$ is $(k-1)$-colorable; however, the coloring $\phi$ used on $R$ cannot be extended to a proper $(k-1)$-coloring of $R'$ by construction.  The extension $R'$ is, in fact, a minimal subset of $V(G)$ to which $\phi$ cannot be extended.

Finally, we define a \emph{complete} critical extension.  The extension $R'$ is complete if both $G[R'-R]=W[R'-R]$ and there is a one-to-one correspondence between edges in $W$ from $R'-R$ to $X$, to edges in $G$ from $R'-R$ to $R$.  If an extension is complete, then the edge contribution in Lemma \ref{lem:CriticalExt} is the same on each side of Equation \ref{eq:CritExtBasic}.  That is,
\[|E(G[R'])|=|E(G[R])|+|E(W)|-|E(K_{|X|})|.\]
For a general $W$-critical extension $R'$, it is possible that the left hand side of the above equation is larger. If we have $|E(G[R'])|=|E(G[R])|+|E(W)|-|E(K_{|X|})|+i$ then we say that the extension is \emph{$i$-incomplete}.


\section{Collapsible sets and edge-additions}
Given a graph $G$ and a subset of its vertices $R\subseteq V(G)$, the \emph{boundary} of $R$, denoted by $\partial_G R$, is defined to be the set $\partial R:=\{v\in R\mid uv\in E(G)$ for some $u\in V(G)-R\}$.  If $R$ is a subset of the vertices of two graphs $G$ and $H$, we will specify $\partial_G R$ and $\partial_H R$ for the boundary of $R$ in each respective graph.
\begin{definition}
A proper vertex subset $R$ is \emph{collapsible in $G$} if for every proper $(k-1)$-coloring of $R$, the vertices of $\partial R$ receive the same color.
\end{definition}
We call such a set collapsible, because the subset $R$ behaves like a fat vertex with respect to coloring.

\begin{proposition}\label{prp:CollapsibleProp}
A subset $R\subsetneq V(G)$ is collapsible in $G$ if and only if every critical extension has a core of size 1, is spanning, and is complete.
\end{proposition}
\begin{proof}
Suppose, first, that $R$ is collapsible in $G$.  Let $\phi$ be an arbitrary proper $(k-1)$-coloring of $G[R]$.  Permute the colors, if necessary, so that $\partial R$ receives color 1, and consider the graph $G_{R,\phi}$ and a $W$-critical extension $R'$.  The vertex $x_1\in V(G_{R,\phi})$ is a cut-vertex.  Let $A=(V(G)-R)\cup\{x_1\}$.  Because a $k$-critical graph cannot contain a cut-vertex and must have at least $k$ vertices, we know that $W$ is a subgraph of $G_{R,\phi}[A]$ and that the core $X$ contains only $x_1$.

Now suppose, for sake of contradiction, that $R'\subsetneq V(G)$ and let $y\in V(G)-R'$.  Then we can properly $(k-1)$-color $G-\{y\}$ with $\psi$; this induces a proper $(k-1)$-coloring in $R$ and, without loss of generality, we assume that $\psi(\partial R)=1$.  It follows that using $\psi$ to color $W-\{x_1\}$ and coloring $x_1$ with $1$ gives a proper $(k-1)$-coloring of $W$.  Therefore, we have shown that $R'$ has core size 1 and is spanning, and we now show that it is complete.

If $G[R'-R]$ has an edge $f$ that is not in $W[R'-R]$, then we can properly $(k-1)$-color $G-f$ with $\psi$ and the same argument as above gives a proper $(k-1)$-coloring of $W$.  Suppose that an edge $ux_1\in E(W)$ corresponds to two edges $uv_1,uv_2\in E(G)$ with $v_1,v_2\in R$.  Then $G-uv_1$ can be $(k-1)$-colored by $\psi$. Because $R$ is collapsible, $\psi(v_1)=\psi(v_2)$ is distinct from $\psi(u)$ and thus $\psi$ is actually a proper $(k-1)$-coloring of $G$ which is a contradiction.  Therefore, $R'$ must also be a complete extension.  Because $R'$ and $\phi$ were chosen arbitrarily, this shows the forward direction of the proposition.

We now prove the reverse implication.  Suppose, for sake of contradiction, that every $W$-critical extension of $R$ has a core of size 1, is spanning, and is complete and that $\phi$ is a proper $(k-1)$-coloring of $R$ where $\phi(u)\neq\phi(v)$ for $u,v\in \partial R$.  Without loss of generality, we may assume that $\phi(u)=1$ and $\phi(v)=2$.  We pick a $W$-critical extension $R'$ with core $X$.  Because $|X|=1$ we may assume that $x_2\notin X$.  Because $v\in\partial R$ and $R'$ is spanning, there is an edge $zv$ in $G$ from $R'-R$ to $R$ that has no corresponding edge in $W$ as $x_2\notin V(W)$.  Therefore $R'$ is at least 1-incomplete, which is a contradiction.
\end{proof}


\begin{lemma}\label{lem:MinimalNo2Cut}
There is no 2-cut in a minimal counterexample to the third statement of Theorem \ref{thm:main}.
\end{lemma}
\begin{proof}
Let $G$ be a minimal counterexample to the third statement of Theorem \ref{thm:main}. Suppose that there is a 2-cut $\{x,y\}$.  Then by Dirac \cite{D53} deleting $\{x,y\}$ leaves us with two components $H_1$ and $H_2$, $\tilde{G_1}=G-H_2$ is $(k-1)$-colorable by $\phi$ where $\phi(x)=\phi(y)$, and $\tilde{G_2}=G-H_1$ is $(k-1)$-colorable by $\psi$ where $\psi(x)\neq\psi(y)$.
We could claim that $G$ is an Ore composition of $\tilde{G_1}+xy$ and $\tilde{G_2}/\underline{xy}$ if we are able to show that $x$ and $y$ have no common neighbors in $\tilde{G_2}$.

Suppose that $z$ is such a vertex.  Then $G-xz$ is $(k-1)$-colorable by $\phi$ and because $\tilde{G_1}\subseteq G-xz$, $\phi(x)=\phi(y)$.
However, $\phi(z)\neq\phi(y)$ because they are adjacent and so $\phi$ is also a proper $(k-1)$-coloring of $G$.
This is a contradiction, so no such $z$ exists. Thus we have shown that $G$ is an Ore composition of $\tilde{G_1}+xy$ and $\tilde{G_2}/\underline{xy}$, which we rename to $G_1$ and $G_2$ (respectively) for the remainder of the proof.

Because $G$ is not $k$-Ore, at most one of $G_1$ and $G_2$ is $k$-Ore.
First, suppose that $G_2$ is not $k$-Ore.
Any time we have an Ore composition of graphs we know that
\[\rho(G)=\rho(G_1)+\rho(G_2)-k^2+3k-\epsilon+\delta\left(T(G_1)+T(G_2)-T(G)\right).\]
By Lemma \ref{lem:TGcompose} and because $G_2$ is not $k$-Ore, it follows that $\rho(G)\leq \rho(G_1)-2(k-1)-\epsilon+2\delta\leq\rho(G_1)$.
Therefore $G_1$ must be $k$-Ore because it is smaller than $G$. If $G_1\neq K_k$ and $|V(G_1)|=n$, then the second assertion of Theorem \ref{thm:main} yields 
\[\rho(G)\leq \left(k(k-3)+n\epsilon-(n-1)\frac{\delta}{k-1}-2\delta\right)-2(k-1)-\epsilon+2\delta\]
\[=k(k-3)-2(k-1)+(n-1)\left(\epsilon-\frac{\delta}{k-1}\right)\leq k(k-3)-2(k-1),\]
which is a contradiction. 
So it follows that $G_1$ must be $K_k$.  But in this case Lemma \ref{lem:TGcompose} gives $T(G_1)+T(G_2)-T(G)\leq1$, so we get
$\rho(G)\leq(k(k-3)+k\epsilon-2\delta)-2(k-1)-\epsilon+\delta.$
Because $\delta\geq(k-1)\epsilon$, this is a contradiction.  
The argument works exactly the same when we assume that $G_1$ is not $k$-Ore.
Therefore we have shown that a minimal counterexample $G$ must be at least 3-connected.
\end{proof}

\begin{definition}
Let $G$ be a $k$-critical graph. An \emph{edge-addition} in $G$ is a non-edge $xy$ such that for some $k$-critical graph $H$ with 
$xy\in E(H)$, $H-xy\subseteq G$ and $V(H)\subsetneq V(G)$.
\end{definition}

Note that if a $k$-critical graph $G$ has a collapsible subset $R\subsetneq V(G)$ then $G$ admits an edge-addition.  The connectivity of a $k$-critical graph means $|\partial_G R|\geq2$ and $R$ collapsible implies that $xy$ is an edge addition in $G$ for $x,y\in\partial_G R$.

\begin{lemma}\label{lem:MinimalNoEdgeAddition}
A minimal counterexample $G$ to the third statement of Theorem \ref{thm:main} admits no edge-addition.
\end{lemma}
\begin{proof}
Let $G$ be a $k$-critical graph such that $G$ is not $k$-Ore, $\rho(G)>k(k-3)-2(k-1)$, and $G$ is the smallest $k$-critical graph that satisfies (1) and (2). 
Suppose, for sake of contradiction, that there is a non-edge $xy$ such that $G+xy$ contains a $k$-critical subgraph $H$ where $V(H)\subsetneq V(G)$, .

Of all the edge-additions that exist in $G$, pick $xy$ so that we minimize the number of vertices in the $k$-critical subgraph $H$.  Let $R=V(H)$.  
Then $\rho_G(R)\leq\rho(H)+2(k-1)+\delta$ where equality implies that $xy$ is in a $K_{k-1}$ or $K_{k-2}$ subgraph counted by $T(H)$.
Because $R$ is a proper subset, we can make a $W$-critical extension $R'$ and by Corollary \ref{cor:ExtensionDrop} we have
\begin{equation}\label{eq:EdgeAddition}
\rho_G(R')\leq\rho_G(R)-2(k-1)-\delta\leq \rho(H).
\end{equation}
Since $\rho(G)\leq\rho_G(R')\leq\rho(H)$ and $H$ is smaller than $G$, it follows that $H$ must be $k$-Ore and $\rho(H)\leq k(k-3)$.

We show now that $R$ must also be collapsible in $G$.  If $R$ is not collapsible, then we may assume that we chose the $W$-critical extension $R'$ so that it is either not spanning, not complete, or has core of size larger than 1.  If $R'$ is not spanning then we can make another extension and by Corollary \ref{cor:ExtensionDrop} and Equation \ref{eq:EdgeAddition} we have $\rho(G)\leq\rho_G(R'')\leq \rho(H)-2(k-1)-\delta\leq k(k-3)-2(k-1)$, which is a contradiction. If $R'$ is $i$-incomplete for $i\geq1$ then, because each uncounted edge lowers the potential $\rho_G(R')$ by $2(k-1)$, we get $\rho(G)\leq\rho_G(R')\leq\rho(H)-i2(k-1)$. This is also a contradiction.  Finally, if the $W$-critical extension $R'$ has a core of size larger than 1 then by Fact \ref{fct:CompletePotential} $\rho(K_{|X|})$ is minimized when $|X|=k-1$ rather than when $|X|=1$.
One can check that using $|X|=k-1$ instead of $|X|=1$ in Corollary \ref{cor:ExtensionDrop} implies that
\[\rho_G(R')\leq\left[\rho_G(R)-2(k-1)-\delta\right]-(k^2-5k+6+(k-2)\epsilon-(k-2)\delta).\]
Using Equation \ref{eq:EdgeAddition}, and because $2(k-1)\leq k^2-5k+6+(k-2)\epsilon-(k-2)\delta$ when $k\geq6$, it follows that
$\rho_G(R')\leq\rho(H)-2(k-1)\leq k(k-3)-2(k-1)$, which is a contradiction.
Therefore, we have shown by Proposition \ref{prp:CollapsibleProp} that $R$ is collapsible in $G$.

By Lemma \ref{lem:MinimalNo2Cut} there is no 2-cut in $G$, so $|\partial R|\geq3$ and we can say $w\in\partial R-\{x,y\}$.
Suppose $H=K_k$.  
Then $G[R]=K_k-e$ and because $|\partial R|\geq3$ it is not possible for $R$ to be collapsible since the largest color class of any proper $(k-1)$-coloring of $K_k-e$ is 2.
Therefore, we may assume that $H$ is an Ore composition of $k$-Ore graphs $H_1$ and $H_2$ with overlap vertices $\{a,b\}$.  By the minimality of $H$, $xy\in E(H_1)$.

Because there is no 2-cut in $G$, then there must be $u,v\in\partial R$ such that $u\in V(H_1)-V(H_2)$ and $v\in V(H_2)-V(H_1)$.
Now consider a proper $(k-1)$-coloring $\phi$ of $G[R]$.  We know that $\phi(u)=\phi(v)$ because $R$ is collapsible, and that $\phi(a)\neq\phi(b)$.
Without loss of generality, let $\phi(a)=1$ and $\phi(b)=2$.
If $\phi(u)\notin\{1,2\}$, then we may assume that $\phi(u)=3$.  In this case, switching the colors 3 and 4 on $H_1$ only will yield a proper $(k-1)$-coloring of $G[R]$ in which $u$ and $v$ receive different colors, which is a contradiction.
Otherwise, we may assume that $\phi(u)=1$. Now either $\phi(v)=\phi(a)=1$ in every proper $(k-1)$-coloring of $R$, or we can switch $\phi(v)$ with another color to produce a proper $(k-1)$-coloring of $R$ where $\phi(v)\neq\phi(u)$.
In the latter case we contradict the fact that $R$ is collapsible, and in the former case $av$ is a non-edge of $G$ such that $G+av$ has a $k$-critical subgraph of size at most $|V(H_2)|+1$, which contradicts the minimality of $H$.  Therefore no edge-addition can exist in a minimal counterexample to the third statement of Theorem \ref{thm:main}.
\end{proof}

\begin{corollary}\label{cor:MinimalNoCollapsible}
If $G$ is a minimal counterexample to the third statement of Theorem \ref{thm:main}, then $G$ has no collapsible subsets $R$ with $|R|\geq2$.
\end{corollary}
\begin{proof}
Suppose that $G$ has a collapsible subset $R\subsetneq G$ and that $|R|\geq2$.
Then the connectivity of a $k$-critical graph implies that $|\partial R|\geq2$.  Thus because $R$ is collapsible, for distinct vertices $x,y\in\partial R$ the edge $xy$ is an edge-addition, which is a contradiction.
\end{proof}

Using the definitions of diamond and emerald, we have the following corollary.
\begin{corollary}\label{cor:MinimalNoGems}
A minimal counterexample to the third statement of Theorem \ref{thm:main} cannot have a diamond or emerald.
\end{corollary}
\begin{proof}
If $G$ has a diamond with endpoints $u,v$, then $\{u,v\}$ is a 2-cut, which contradicts Lemma \ref{lem:MinimalNo2Cut}.  If $G$ has an emerald $D$, then let $R=V(G)-V(D)$.  Either $\partial R$ receives only one color in each proper $(k-1)$-coloring of $G[R]$ or there exists some proper $(k-1)$-coloring $\phi$ where $|\phi(\partial R)|>1$.  If such a $\phi$ exists then we can extend $\phi$ to $V(D)$ and properly $(k-1)$ color all of $G$, which is a contradiction.
But if $\partial R$ receives one color in every proper $(k-1)$-coloring of $G[R]$ then for $x,y\in\partial R$ we have that $xy$ is an edge-addition, which contradicts Lemma \ref{lem:MinimalNoEdgeAddition}.
\end{proof}
Note that for a graph $G$ with a subgraph $G'\subseteq G$, it is possible for $D\subseteq G'$ to be a diamond (or emerald) of $G'$ but not be a diamond (or emerald) of $G$.  
For $D$ to be a diamond (or emerald) of both $G$ and $G'$, we need the edges from $V(D)$ to $V(G)-V(D)$ to be the same in $G$ as in $G'$ (although extra edges in $G$ to the endpoints of a diamond are allowable).


\section{Generalization to $i$-collapsible and $(i+1)$-edge-additions}

Now we generalize our previous definitions of collapsible subsets and edge-additions to further examine the structure of a minimal counterexample to the third statement of Theorem \ref{thm:main}.
\begin{definition}
A proper vertex subset $R\subsetneq V(G)$ is \emph{$i$-collapsible} in $G$ if for all proper $(k-1)$-colorings $\phi$ of $G[R]$ using color set $C$
\begin{equation}\label{eq:iCollapseEquation}
\min_{c\in C}\left|\left\{uv\in E(G)\mid u\in\phi^{-1}(C-c)\cap R \textrm{ and } v\in V(G)-R\right\}\right|\leq i.
\end{equation}
\end{definition}
Thus, a proper vertex subset $R$ is $i$-collapsible if there is a majority color class in $\phi(\partial_GR)$ which covers all but at most $i$ edges from $R$ into $V(G)-R$.
Note that 0-collapsible sets correspond to our previous definition of collapsible sets.  We also generalize the definition of edge-addition such that $i=0$ corresponds to the previous definition of edge-addition.

\begin{definition}
Let $G$ be a $k$-critical graph.  An \emph{(i+1)-edge-addition} in $G$ is a set $S$ of at most $(i+1)$ non-edges such that there exists a $k$-critical graph $H$ with $S\subseteq E(H)$, $H-S\subseteq G$, and $V(H)\subsetneq V(G)$.
\end{definition}
Note that because no proper subgraph of $G$ is $k$-critical, a 1-edge-addition cannot come from a set of 0 edges.  Thus, this definition for $i=0$ is identical to the previous definition of edge-addition.



\begin{proposition}\label{prp:WheniCollapsible}
If $R\subsetneq V(G)$ is a vertex subset where all $W$-critical extensions of $R$ are spanning, have core size 1, and are at most $i$-incomplete then $R$ is $i$-collapsible in $G$.
\end{proposition}
\begin{proof}
To show that $R$ is $i$-collapsible in $G$ we need to show that Equation \ref{eq:iCollapseEquation} holds for all proper $(k-1)$-colorings of $R$.  Let $\phi$ be an arbitrary proper $(k-1)$-coloring using color set $C$ and let $R'$ be a $W$-critical extension using that coloring.  
By hypothesis, $R'=V(G)$ and we may permute colors of $\phi$ so that the core of the extension is the vertex $x_1$.
Thus each edge from $\phi^{-1}(C-\{1\})\cap R$ to $V(G)-R$ is counted by $|E(G[R'])|$ but not by $|E(G[R])|+|E(W)|-|E(K_{|X|})|$.  Because $R'$ is at most $i$-incomplete, there can be at most $i$ such edges.
Therefore 
\[\left|\left\{uv\mid u\in\phi^{-1}(C-\{1\})\cap R \text{ and } v\in V(G)-R\right\}\right|\leq i.\]
and by definition $R$ is $i$-collapsible.
\end{proof}

The following is an extension of a result (Lemma 16) in \cite{KY2014}.

\begin{proposition}\label{prp:iCollapsiblei1EdgeAddition}
If $G$ is a $k$-critical graph with a $i$-collapsible subset $R\subsetneq V(G)$ for $i\leq(k-3)/2$ then $G$ admits an $(i+1)$-edge-addition.
\end{proposition}
\begin{proof}
Let $G$ be a $k$-critical graph and let $R\subsetneq V(G)$ be an $i$-collapsible subset for $i\leq(k-3)/2$.  Suppose, for sake of contradiction, that $G$ admits no $(i+1)$-edge-addition.  For each $u\in\partial R$, let $w(u)=|\{uv\in E(G)\mid v\in V(G)-R\}|$.  Because $G$ is a $k$-critical graph, it is $(k-1)$-edge-connected and thus $\sum_{u\in\partial R}w(u)\geq k-1$.

Now $w:\partial R\rightarrow \{1,2,\ldots\}$ is an integral positive weight function that satisfies the hypotheses of Lemma 16 from \cite{KY2014}.  Therefore, for each $0\leq i\leq (k-3)/2$ there exists a graph $H$ with $V(H)=\partial R$ and $|E(H)|=i+1$ such that for every independent set $M$ in $H$ with $|M|\geq2$
\[\sum_{u\in\partial R-M}w(u)\geq i+1.\]
That means that because $G$ admits no $(i+1)$-edge addition, $G[R]+E(H)$ is $(k-1)$-colorable using color set $C$ by $\phi$.
But $\phi$ is also a proper $(k-1)$-coloring of $G[R]$ and, further, every color class $c\in C$ of size at least 2 has
\[|\{uv\in E(G)\mid u\in \phi^{-1}(C-c)\cap R\text{ and }v\in V(G)-R\}|\geq i+1.\]
This does not immediately contradict that $R$ is $i$-collapsible, because it gives no information about color classes of size 1.
To complete the proof, we now examine the cases in \cite{KY2014} more closely.

Let $\partial R=\{u_1,\ldots,u_s\}$ and, without loss of generality, assume that $w(u_1)\geq w(u_j)$ for all $2\leq j\leq s$.
\begin{case}
Suppose $w(u_2)+\cdots+ w(u_s)\geq i+2$.
\end{case}
For this case, we may further assume that $w(u_1)\geq w(u_2)\geq\cdots\geq w(u_s)$.
Choose the largest $j$ such that $w(u_j)+\cdots w(u_s)\geq i+1$.  Let $\alpha=(i+1)-(w(u_{j+1})+\cdots+w(u_s))$.  Therefore $\alpha\leq w(u_j)$.  Since $i\leq(k-3)/2$ and $w(u_1)+\cdots+w(u_s)\geq k-1$, we also have $w(u_1)+\cdots+w(u_j)\geq i+1+\alpha$.  By the choice of $j$ and the ordering of the vertices, $0<\alpha\leq w(u_j)\leq w(u_1)$.  We draw $\alpha$ edges each connecting $u_1$ with $u_j$ and $i+1-\alpha$ edges connecting $\{u_{j+1},\ldots,u_s\}$ with $\{u_1,\ldots,u_j\}$ so that for each $\ell$, the degree of $u_\ell$ in the obtained multigraph $H$ is at most $w(u_\ell)$.  Because $G$ admits no $(i+1)$-edge-addition this gives a proper $(k-1)$-coloring $\phi$ of $G[R]+E(H)$ using color set $C$, which is also a proper $(k-1)$-coloring of $G[R]$.  Let $c\in C$ be any color class. 

Since $\phi^{-1}(c)$ is independent, it follows that
\[\sum_{u\in\partial R-\phi^{-1}(c)}w(u)\geq\sum_{u\in\partial R-\phi^{-1}(c)}d_H(u)\geq\frac{1}{2}\sum_{u\in\partial R}d_H(u)=i+1.\]
This contradicts the fact that $R$ is $i$-collapsible in $G$.

\begin{case}
Suppose $w(u_2)+\cdots+ w(u_s)\leq i+1$.
\end{case}
We let $E(H)=\{u_1u_j\mid 2\leq j\leq s\}$.  Because $G$ admits no $(i+1)$-edge-addition this gives a proper $(k-1)$-coloring of $G[R]+E(H)$ using color set $C$, which is also a proper $(k-1)$-coloring of $G[R]$.  If $c$ is any color class not containing $u_1$ then $w(u_1)\geq i+1$, and that color class does not satisfy the definition of $i$-collapsible. Suppose that $\phi(u_1)=1$.  Note that $u_1$ is the only vertex in $\partial R$ that receives color 1, so it follows that $w(u_2)+\cdots+w(u_s)\leq i$ because $R$ is $i$-collapsible. 

Let $\psi$ be a proper $(k-1)$-coloring of $G[(V(G)-R)\cup\{u_1\}]$ such that $\psi(u_1)=1$.  Because $G$ is $k$-critical, $\overline{\psi}=\psi|_{V(G)-R}\cup\phi|_R$ is not a proper coloring.  We pick $\psi$ so that the number of edges from $\partial_G R$ to $V(G)-R$ that have endpoints colored the same by $\overline{\psi}$ is minimized.  Without loss of generality, $\phi(u_2)=2$ and one of its neighbors in $V(G)-R$ also receives color 2.

We will switch color class 2 in $\phi$ with another color class so that $\overline{\psi}$ colors $u_2$ differently than all of its neighbors without increasing the number of edges from $\partial R$ to $V(G)-R$ with endpoints colored the same.  We cannot switch 2 with 1 in $\phi$, so there remains $(k-2)$ choices.  For each of the at most $i$ edges $u_jv$ from $\partial R-\{u_1\}$ to $V(G)-R$, we remove from the set of choices $\phi(u_j)$ if $\phi(u_j)\neq2$ or $\phi(v)$ if $\phi(u_j)=2$.  This leaves at least $k-2-i\geq (k-1)/2\geq 1$ choice.  By switching color class 2 in $\phi$, we contradict our choice of $\psi$.  Thus, either $\overline{\psi}$ is a proper $(k-1)$-coloring of $G$ or $R$ is not $i$-collapsible, and we have completed the proof.
\end{proof}
%ummm...


\begin{lemma}\label{lem:TightGeneralEdgeAddition}
In a minimal counterexample $G$ to the third statement of Theorem \ref{thm:main}, there is no proper subset $R\subsetneq V(G)$ with $|R|\geq 2$ and $\rho_G(R)<\rho(G)+2(i+1)(k-1)+\delta$ for $1\leq i\leq\frac{k-4}{2}$.  Further, $G$ does not admit an $i$-edge-addition for $1\leq i\leq\frac{k-4}{2}$.

%Moreover, if $P+Q\geq a$ then there does not exist a proper subset $R\subsetneq V(G)$ such that $\rho_G(R)<\rho(G)+k^2-3k+4$ (EPSILON/DELTAS?)
%and there are no $i$-edge additions for $i\leq\frac{k-2}{2}$.
%worry.....%%$1\leq i\leq\frac{k-2}{2}$.???Something weird happens at boundary.
\end{lemma}
\begin{proof}
We prove this by induction on $i$.  First we examine the case where $i=1$. Lemma \ref{lem:MinimalNoEdgeAddition} shows that there is no 1-edge addition.


Now suppose, for sake of contradiction, that $R\subsetneq V(G)$ is a proper vertex subset where $\rho_G(R)<\rho(G)+4(k-1)+\delta$.  Taking an arbitrary $W$-critical extension $R'$, Corollary \ref{cor:ExtensionDrop} gives us $\rho_G(R')\leq\rho_G(R)-2(k-1)-\delta <\rho(G)+2(k-1)$.
If the extension is not spanning then we can extend again and get $\rho_G(R'')<\rho(G)$, which is not possible.  If the extension is not complete, then we lose at least an extra $2(k-1)$ when extending from $R$ to $R'$.  This gives $\rho_G(R')<\rho(G)$ which is not possible.  Lastly, if the core of the extension $R'$ has size larger than 1, then the potential equation for an extension (Equation \ref{eq:ExtensionPotential}) in Corollary \ref{cor:ExtensionDrop} uses $|X|=k-1$ rather than $|X|=1$.
Using Fact \ref{fct:CompletePotential}, one can check that, for $k\geq 6$, the potential of the extension goes down at least an additional $2(k-1)$.
Again, this implies that $\rho_G(R')<\rho(G)$ which is not possible.
Therefore, we have shown that $R$ is a collapsible set in $G$ which contradicts Corollary \ref{cor:MinimalNoCollapsible}.

We now prove this for general $i$.  The inductive hypothesis is that there is no proper subset $R$ of size at least 2 and $\rho_G(R)<\rho(G)+2i(k-1)+\delta$ and, further, there are no $j$-edge-additions for $j<i$.  For sake of contradiction, we assume that $R$ is a proper subset of size at least 2 and that $\rho_G(R)<\rho(G)+2(i+1)(k-1)+\delta$.  By Corollary \ref{cor:ExtensionDrop}, a $W$-critical extension $R'$ has potential $\rho_G(R')\leq\rho_G(R)-2(k-1)-\delta<\rho(G)+2i(k-1)$.  The inductive hypothesis implies that $R'=V(G)$, so all extensions are spanning.  Also, because $\rho(G)=\rho_G(R')$, the right hand side of the inequality cannot drop by $2i(k-1)$, and so the extension can be at most $(i-1)$-incomplete.
If the core of $R'$ has size larger than 1, then Equation \ref{eq:ExtensionPotential} becomes
\[\rho_G(R')\leq\rho_G(R)+\rho(W)-(2k^2-6k+4+(k-1)\epsilon-2\delta).\]
Because $\rho(G)=\rho_G(R')$ we can use the assumption on $\rho_G(R)$ and the bound $i\leq\frac{k-4}{2}$ to obtain the following inequality:
\[\rho(G)<\rho(G)+2(i+1)(k-1)+\delta+\rho(W)-(2k^2-6k+4+(k-1)\epsilon-2\delta)\]
which simplifies to
\[0<-k^2+3k-2+3\delta-(k-1)\epsilon+\rho(W).\]
Whether $W$ is $k$-Ore or not, it is a smaller $k$-critical graph than $G$ so by Theorem \ref{thm:main} the right hand side of the inequality is negative, which is a contradiction.  Therefore, the core of the extension $R'$ has size 1.

By Proposition \ref{prp:WheniCollapsible}, $R$ is $(i-1)$-collapsible.  Since every proper subset of size at least 2 with $\rho_G(R)<\rho(G)+2(i+1)(k-1)+\delta$ is $(i-1)$-collapsible by the above argument, we may assume that we chose an $(i-1)$-collapsible set $R$ of minimal size.  By Proposition \ref{prp:iCollapsiblei1EdgeAddition}, $G$ admits an $i$-edge-addition and $H\subseteq G[R]+S$is a $k$-critical subgraph.  Because $G$ does not admit an $(i-1)$-edge-addition, $|S|=i$.

Pick a set $S$ of exactly $i$ edges that minimizes the order of $k$-critical graph $H\subseteq G[R]+S$.
Let $R_0=V(H)$; then $\rho_G(R_0)\leq\rho(H)+2i(k-1)+i\delta$.

First, we suppose that $H$ is not $k$-Ore.
Then because $H$ is smaller than $G$, $\rho(H)\leq k(k-3)-2(k-1)<\rho(G)$.  Thus, like $R$, $R_0$ is a proper subset of size at least 2 with $\rho_G(R_0)<\rho(G)+2(i+1)(k-1)+\delta$.  Also $R_0\subseteq R$, so by the minimality of $R$ it follows that $R=R_0$.

As before, every extension of $R$ is spanning, has core size 1, and is at most $(i-1)$-incomplete.  Further, there must be some extension $R'$ that is $(i-1)$-incomplete.  Otherwise, all extensions are at most $(i-2)$-incomplete and by Proposition \ref{prp:WheniCollapsible} there is a $(i-1)$-edge-addition, which would contradict the inductive hypothesis.  Choose such an $(i-1)$-incomplete extension $R'$ and examine the potential $\rho_G(R')$.
Because $R'$ is a spanning and $(i-1)$-incomplete extension, Lemma \ref{lem:CriticalExt} and the $i$-edge addition in $G[R]$ give that
\[\rho(G)=\rho_G(R')\leq\rho_G(R)+\rho(W)-2(i-1)(k-1)-(k^2-k-2+\epsilon-\delta)\]
\[\leq\rho(H)+2i(k-1)+i\delta+\rho(W)-2(i-1)(k-1)-(k^2-k-2+\epsilon-\delta)\]
\[<\rho(G)+\rho(W)+(i+1)\delta-\epsilon+2(k-1)-k^2+k+2.\]
This calculation shows that $0<\rho(W)-k^2+3k+(i+1)\delta-\epsilon$.  If $W$ is not $k$-Ore, then this is a contradiction because $2(k-1)>(i+1)\delta-\epsilon$.  Therefore $W$ is $k$-Ore.  
Because $|X|=1$, Lemma \ref{lem:kOreAwayFromVertex} implies that there is a diamond or an emerald $D$ in $W-\{X\}$.  If it is a diamond, then this is a 1-edge addition in $G$, which contradicts Lemma \ref{lem:MinimalNoEdgeAddition}.  If it is an emerald, then for each $u_i\in V(D)$ we have $\deg_{W-\{X\}}(u)=k-1$.  However, in $G$, there could be other edges incident to $u_i$ namely, those that cause the $(i-1)$-incompleteness of $R'$.  So at least $(k-1)-(i-1)=k-i$ vertices $u_i\in V(D)$ have degree $k-1$ in $G$.  

Suppose that $u_1,\ldots, u_\ell$ are the vertices with $\deg_G(u_i)=k-1$.  
For each $i$ in $1\leq i\leq\ell$, label the unique vertex in $N_G(u_i)-V(D)$ as $v_i$.  
If any $v_i\neq v_j$ for $1\leq i<j\leq\ell$, then $v_iv_j$ is an edge-addition in $G$.  
To see this, we properly $(k-1)$-color $G-\{u_i,u_j\}$.  
There are two colors not used on the partial coloring of $D$, suppose they are $1$ and $2$.  
If $\phi(v_i)\in\{1,2\}$ then we color $u_j$ with $\phi(v_i)$ and color $u_i$ with the other.  
Otherwise, we can greedily color $u_j,u_i$ in that order.  
Either way, we have obtained a proper $(k-1)$-coloring of $G$.  
Therefore, $v_1=v_2=\cdots=v_\ell$.  
Adding an edge from $v_1$ to each of $u_{\ell+1},\ldots,u_{k-1}$ yields a $K_k$.  
This $(i-1)$-edge-addition is a contradiction.


Therefore, the graph $H$ obtained by adding $i$ edges to $G[R]$ must be $k$-Ore.  Recall that we chose the set $|S|$ of $i$ edges to minimize the order of $H$.  We first examine the case where $H$ is not $K_k$ and then the case where $H=K_k$.

If $H$ is not $K_k$, then $H$ is an Ore composition of $k$-Ore graphs $H_1$ and $H_2$ with overlap vertices $\{a,b\}$.  Let $\overline{S}=S\cap E(H_1)$ be the new edges on the edge-side of the composition.  If $|\overline{S}|\leq i-2$ then $\overline{S}\cup\{ab\}$ is a $(i-1)$-edge-addition, which is a contradiction.  If $|\overline{S}|=i-1$ then $\overline{S}\cup\{ab\}$ is a $i$-edge-addition that contradicts the minimal order of $H$.  Therefore $S\subseteq E(H_1)$ and $H_2-\{\underline{ab}\}\subseteq G$.  By Lemma \ref{lem:kOreAwayFromVertex} there is a diamond or an emerald $D$ in $H_2-\{\underline{ab}\}$ away from the split-vertex of the composition.  If $D$ is a diamond, then it admits a $1$-edge-addition which is also a $1$-edge-addition in $G$.  This contradicts Lemma \ref{lem:MinimalNoEdgeAddition}.

Therefore $D$ is an emerald of $H_2-\{\underline{ab}\}$; however, $D$ is not necessarily an emerald in $G$ because a vertex in $V(D)$ could lie in $\partial_G R$.  In any proper $(k-1)$-coloring of $G[R]$, the vertices $V(D)=\{u_1,u_2\ldots,u_{k-1}\}$ all receive different colors.  Recall that $R'$ has core size 1, is spanning, and is at most $(i-1)$ incomplete; thus, there are at most $i$ vertices in $V(D)\cap\partial_G R$, since only one can share a color with $X$.  Let $u_1,\ldots,u_\ell$ be the vertices in $V(D)-\partial_G R$.  These vertices have a common neighbor $v_1$ outside of $V(D)$, otherwise we have a $1$-edge-addition.  Adding an edge from $v_1$ to each $u_i$ with $\ell<i\leq k-1$ is an $i$-edge-addition which gives a $K_k$ and thus contradicts the minimality of $H$.

Now we turn to the case where $H=K_k$.  Let $V(H)=\{u_1,\ldots,u_k\}$ and note that $G[R]+S=H$ by the minimality of $R$.  We label the vertices so that $u_1u_k\in S$. 
Thus we can properly $(k-1)$-color $G[R]$ with $\phi$ using color set $C=[k-1]$ such that $\phi(u_i)=i$ for $1\leq i\leq k-1$ and $\phi(u_k)=1$.
Because $R$ is $(i-1)$-collapsible in $G$, we have
\begin{equation}\label{eq:i-1Collapse}
\min_{c\in C}\left|\left\{uv\in E(G)\mid u\in\phi^{-1}(C-c)\cap R \text{ and } v\in V(G)-R\right\}\right|\leq i-1.
\end{equation}
Note that $\deg_H(u)=k-1$ for any $u\in R$, and because $G$ is a $k$-critical graph we have $\deg_G(u)\geq k-1$ as well.
Thus, for each $u\in R$ there are at least as many edges of $G$ from $u$ to $V(G)-R$ as the number of edges of $S$ incident with $u$.
This means that 
\[\left|\left\{uv\in E(G)\mid u\in\phi^{-1}(C-c)\cap R\text{ and }v\in V(G)-R\right\}\right|\geq i\]
 for each $c\neq1$ and so that color class does not witness Equation \ref{eq:i-1Collapse}.
It follows that the color class $c=1$ must witness Equation \ref{eq:i-1Collapse} and, hence, must cover all but at most $i-1$ endpoints of edges in $S$.

This implies that every edge in $S-\{u_1u_k\}$ is incident to either $u_1$ or $u_k$.
If $u_1u_2$ and $u_ku_3$ are both in $S$, then we can switch the labels $u_2$ and $u_k$.
Then no color class covers all but at most $i-1$ endpoints of edges in $S$ and we obtain a contradiction.
Therefore $S$ either forms a star subgraph, or $|S|=3$ and $S$ forms a triangle subgraph.  We examine these cases separately.

Suppose that $S$ is a star and that $u_1$ is the center of the star.  
In this case we show that $G[R-\{u_1\}]$ is an emerald in $G$, which is a contradiction.
In order to satisfy Equation \ref{eq:i-1Collapse} each leaf of the star has exactly one edge to $V(G)-R$ and every $u\in R$ not incident with $S$ has no edges to $V(G)-R$.
Therefore $\deg_G(u_i)=k-1$ for $2\leq i\leq k$ and, by definition, $G[R-\{u_1\}]$ is an emerald in $G$.

Suppose that $S$ is a triangle and that $S=\{u_1u_2,u_2u_3,u_1u_3\}$.
In order to satisfy Equation \ref{eq:i-1Collapse} for any proper $(k-1)$-coloring of $G[R]$ each $u_i$ for $1\leq i\leq3$ has exactly two edges to $V(G)-R$ and every $u\in R$ not incident with $S$ has no edges to $V(G)-R$.
However, by assumption of the lemma, $i=3$ implies that $k\geq10$.
This is a contradiction because $k$-critical graphs are $(k-1)$-edge-connected, and there are only 6 edges from $R$ to $V(G)-R$.
This contradiction completes the proof.
\end{proof}


\begin{corollary}\label{cor:ProperPotential}
In a minimal counterexample to the third statement of Theorem \ref{thm:main} $G$, any proper vertex subset $R\subsetneq V(G)$ with $|R|\ge2$ has potential
$\rho_G(R)\geq\rho(G)+k^2-3k+2+\delta$.
\end{corollary}
\begin{proof}
By Lemma \ref{lem:TightGeneralEdgeAddition}, $\rho_G(R)\geq\rho(G)+2(i+1)(k-1)+\delta$ for all $i\leq\frac{k-4}{2}$.  One can check that this implies that $\rho_G(R)\geq\rho(G)+k^2-3k+2+\delta$ as claimed.
\end{proof}


We are also able to get degree conditions on neighbors of vertices of low degree, which will be frequently used when discharging.


\begin{lemma}\label{lem:NeighborsDiffer}
In a minimal counterexample $G$ to the third statement of Theorem \ref{thm:main}, let $x$ and $y$ be adjacent vertices such that $\deg_G(x)=k-1$ and $N_G[x]$ is not a subset of $N_G[y]$.  Then $\deg_G(y)\geq|N_G(x)\cap N_G(y)|+1+\frac{k-3}{2}$.
\end{lemma}
\begin{proof}
Suppose that $G$ is a minimal counterexample to the third statement of Theorem \ref{thm:main}
and let $x$ and $y$ be adjacent vertices such that $\deg_G(x)=k-1$ and let $w\in N_G[x]-N_G[y]$.

For any proper $(k-1)$-coloring of $G-\{x\}$, the vertices of $N_G(x)$ must all receive distinct colors.
Further, it is not possible to switch the color of $y$ to match $w$.
Therefore, for any proper $(k-1)$-coloring $\phi$ of $G-\{x\}$, there must be some vertex in $N_G[y]-N_G[x]$ which is colored with $\phi(w)$.

If we add edges from $w$ to every vertex in $N_G[y]-N_G[x]$, this creates a $k$-critical subgraph of $G-\{x\}$.
Therefore $|N_G[y]-N_G[x]|\geq\frac{k-3}{2}$, because otherwise we contradict Lemma \ref{lem:TightGeneralEdgeAddition}.
This gives the desired bound on $\deg_G(y)$.
\end{proof}
