\mychapter{Discharging}

In this chapter, we complete the proof of the third statement of Theorem \ref{thm:main} using a discharging argument.  The method of discharging, described very elucidatingly in \cite{CW2013}, is a global versus local argument.  We use potential as a global measure on the graph, and have already shown how certain local structures (2-vertex cuts, $i$-edge-additions, $i$-collapsible sets, etc.) are not allowed in a minimal $k$-critical graph which is not $k$-Ore and has potential greater than $k(k-3)-2(k-1)$.  There still remain areas of low potential such as gadgets or clusters of size $k-3$, and the goal of this chapter is to show how the local structure at these areas contradicts the global hypothesis on potential.  We will give each vertex charge relative to its degree, and then spread that charge throughout the graph using bounds obtained in previous chapters.  The goal of a general discharging argument is to give each vertex charge which is not positive.  This will lead to a contradiction, whereby the total charge on the minimal counterexample $G$ gives that $\rho(G)>k(k-3)-2(k-1)$ is not possible.

However, we will go through discharging in two stages where only the first stage is done in the traditional style.  In the first stage, we send packets of charge along edges, pushing from areas of high negative charge to areas which have positive initial charge.  This gives a bound on each vertex which does not fall into four specific sets (vertex subsets $L,M,P,$ and $Q$ defined in Definition \ref{def:specialSets}), and also gives us a bound on the global charge of the graph.  However, these bounds only hold for $k\geq33$, which gives the restriction on the third statement of Theorem \ref{thm:main}.  It is possible that the third statement is true for other $k$ as well; however, it would take a much more complex set of discharging rules to handle these cases.  

In the second stage of discharging looks at averaging charge across the graph, letting subsets with negative charge compensate for subsets with positive charge rather than pushing charge along a specific edge.  In the end, these arguments combine with the results of Chapter 2 to give a bound on $2|E(G)|$.  
Using other bounds on this parameter, such as the bound established by Kierstead and Rabern \cite{KR2014}, we will arrive at a contradiction for $\epsilon\leq\frac{4}{k^3-2k^2+3k}$.

%%%!!!!In PrelimChapter FOR MAIN WRITEUP
%The following Lemma, used in the second stage of discharging, is a restatement in terms of $k$-critical graphs of a Theorem from Kierstead and Rabern (Theorem 4.5) \cite{KR2014}.  Let $\text{mic}(G)$ be the maximum of $\sum_{v\in I}\deg_G(v)$ over all independent vertex subsets $I$ of $G$.
%\begin{lemma}\label{lem:KR}
%Given a $k$-critical graph $G$ with at least one vertex of degree $k-1$,
%\[2|E(G)|\geq (k-2)|V(G)|+\text{mic}(G)+1.\]
%\end{lemma}
%%Do I need to explain why the other case isn't possible? !!!
%In this work, we omit the $+1$ because the other two terms scale with $|V(G)|$.


\section{Discharging: set-up and first stage}
Let $G$ be a minimal counterexample to the third statement of Theorem \ref{thm:main}.  We define a charge function $w:V(G)\rightarrow\mathbb{R}$ so that
\[w(v):=(k-2)(k+1)+\epsilon-\deg_G(v)(k-1).\]
Note that $\sum_{v\in V(G)}w(v)=\rho(G)+\delta T(G)\geq\rho(G)$. 
Below, we show the initial charge for vertices of varying degrees in $G$.
\begin{fact}
\quad
\begin{enumerate}
\item If $\deg_G(v)=k-1$ then $w(v)=k-3+\epsilon$.
\item If $\deg_G(v)=k$ then $w(v)=-2+\epsilon$.
\item If $\deg_G(v)=k+1$ then $w(v)=-k-1+\epsilon$.
\item If $\deg_G(v)=k+\ell$ for $\ell\geq2$ then $w(v)=-2-\ell(k-1)+\epsilon$.
\end{enumerate}
\end{fact}

We now define four disjoint subsets of vertices which will need to be dealt with in the second stage of discharging.  
\begin{definition}\label{def:specialSets}
We define the following \emph{special} vertex subsets.
\[L:=\{v\in V(G)\mid \deg_G(v)=k-1\text{ and }v\text{ has no neighbors of degree }k-1\},\]
\[M:=\{v\in V(G)\mid v\text{ is in a cluster of size 2 and is a lone-vertex}\},\]
\[P:=\{v\in V(G)\mid \deg_G(v)=k\},\]
\[Q:=\{v\in V(G)\mid \deg_G(v)=k+1\}.\]
Further, we remove a vertex $x$ from $L\cup M$ if $x$ is a structure-vertex.  Therefore, $L\cup M$ contains only lone-vertices.
\end{definition}

Let $R$ be the set $V(G)-(L\cup M\cup P\cup Q)$ which contains the rest of the vertices of $G$.
After two stages of discharging we will arrive at a contradiction to our assumption that $\rho(G)>k(k-3)-2(k-1)$.
In the first stage we have two rules to follow.

\textbf{Discharging Rule \#1:} Every vertex of degree at least $k+2$ reserves charge $-2+\epsilon$ and sends the remaining charge equally to all neighbors.
% of degree $k-1$.
Note that a vertex of degree $d$ which follows this rule has charge $k^2-k-d(k-1)$ after reserving $-2+\epsilon$.  Therefore, it sends out charge $\left(\frac{k}{d}-1\right)(k-1)$ to each of its neighbors.

\textbf{Discharging Rule \#2:} Every vertex of degree $k-1$ which is a key vertex of a gadget or in a $K_{k-3}$ sends charge $-(k-1)/t$ to each vertex of an adjacent cluster of size $t<k-3$ which is not a key vertex of a gadget or in a $K_{k-3}$ subgraph.
%!!! if such a vertex $x$ is adjacent to 2 separate clusters, then those clusters (by a cloning x->y) are key vertices in gadgets.

Note that any vertex which follows Rule \#2 is in a cluster of size $s\geq t$ and therefore, by Proposition \ref{prp:OnlyOneNearNeighbor}, sends charge at most $-(k-1)$.


Now let $w'(v)$ be the charge function after applying Rules \#1 and \#2 to $G$.


\begin{lemma}\label{lem:FirstRules}
For every vertex $v\in R=V(G)-\left(L\cup M\cup P\cup Q\right)$ applying Rules \#1 and \#2 give $w'(v)\leq -2+\epsilon$.
\end{lemma}
\begin{proof}
We need to check this for vertices of degree $k+2$ or higher, and also for lone-vertices in a cluster of size $r$ (where $3\leq r\leq k-4$), structure-vertices, and near-vertices in a cluster of size $r\leq k-4$.
We will do this on a case by case basis.
\addtocounter{case}{-2}
\begin{case}
Suppose $\deg_G(v)\geq k+2$.  
\end{case}
Let $v$ be such a vertex. By Rule \#1, $v$ has reserved charge $-2+\epsilon$ and so $w'(v)$ follows the desired inequality.
\begin{case}
Suppose $\deg_G(v)=k-1$ and $v$ is in a cluster of size $r$ $($where $3\leq r\leq k-4)$ which is not adjacent to another cluster.
\end{case}
Let $C$ be a cluster of size $r$ where $3\leq r\leq k-4$, and let $v\in C$.
Because $\deg_G(v)=k-1$, $v$ has $k-r$ neighbors in $V(G)-C$.
Label these vertices $y_1,y_2,\ldots,y_{k-r}$.
By Corollary \ref{cor:CloningStructure}, if any $y_i$ has degree less than $k-1+r$ then we can move to the case where $v$ is in a $K_{k-3}$ subgraph or is a key vertex of a gadget.
Therefore, each $y_i$ follows Rule \#1 and sends charge $\left(\frac{k}{k-1+r}-1\right)(k-1)$ to $v$.  Therefore the new charge of $v$ is $w(v)+\left(\frac{k}{k-1+r}-1\right)(k-1)(k-r)$. One can check that the second derivative of this with respect to $r$ is positive for all $k>1$.  
\[\frac{d^2}{dr^2}[w'(v)]=\frac{2k(1-3k+2k^2)}{(r+k-1)^3}.\]
Therefore, we only need to check that $w'(v)\leq-2+\epsilon$ for the endpoints $r=3$ and $r=k-4$.

When $r=3$, $v$ starts with charge $k-3+\epsilon$ and receives a total of $\frac{-2(k-1)(k-3)}{k+2}$ charge.  
Thus $w'(v)=-k+9-\frac{30}{k+2}+\epsilon$, and for $k\geq8$ we get $w'(v)\leq-2+\epsilon$.

When $r=k-4$, $v$ starts with charge $k-3+\epsilon$ and receives a total of $\frac{(5-k)(k-1)4}{2k-5}$ charge.
Thus $w'(v)=-k+4+\frac{15}{2k-5}+\epsilon$, and for $k\geq8$ we get $w'(v)\leq-2+\epsilon$.

\begin{case}\label{case:KeyVertex}
Suppose $\deg_G(v)=k-1$ and $v$ is a key vertex of a gadget.
\end{case}
Let $v$ be a key vertex of a gadget. 
By Lemma \ref{lem:BoundOnKeyVertex}, $v$ has at least $\frac{k-3}{2}$ neighbors of degree at least $\frac{3}{2}(k-3)+1$; we will call these high-degree neighbors.
For $k\geq 21$, high-degree neighbors have degree at least $\frac{4}{3}k$.
Recall that each high-degree neighbor sends charge $\left(\frac{k}{d}-1\right)(k-1)$, where $d$ is the degree of the vertex, by Rule \#1.
Therefore $v$ gets charge $\frac{-1}{4}(k-1)$ of less from each high-degree neighbor.
Also, by Rule \#2, $v$ may give away, at worst, charge $-(k-1)$ to adjacent near-vertices.  This would raise $w'(v)$ by at most $(k-1)$.
Therefore it follows that
\[w'(v)\leq\frac{-(k-1)}{4}\cdot\frac{k-3}{2}+k-3+\epsilon+(k-1)=\frac{-1}{8}\left(k^2-20k+19\right)-2+\epsilon.\]
For $k\geq19$, we have $w'(v)\leq-2+\epsilon$.

\begin{case}\label{case:Kk-3}
Suppose $\deg_G(v)=k-1$ and $v$ is in a $K_{k-3}$ subgraph.
\end{case}
Let $v$ be a vertex of degree $k-1$ that is in a $K_{k-3}$ subgraph $D$.
By Lemma \ref{lem:BoundOnKk-3}, $v$ has at least $\frac{k-9}{6}$ neighbors of degree at least $\frac{3}{2}(k-3)-1$; we will call these high-degree neighbors.
For $k\geq 33$, high-degree neighbors have degree at least $\frac{4}{3}k$.
Recall that each high-degree neighbor sends charge $\left(\frac{k}{d}-1\right)(k-1)$ by Rule \#1.
Therefore $v$ gets charge $\frac{-1}{4}(k-1)$ of less from each high-degree neighbor.
As long as $v$ does not give away charge by Rule \#2, we have 
\[w'(v)\leq\frac{-(k-1)}{4}\cdot\frac{k-9}{6}+k-3+\epsilon=\frac{-1}{24}\left(k^2-64k+81\right)+\epsilon.\]
For $k\geq33$ it follows that $w'(v)\leq-2+\epsilon$.

If $v$ also gives away charge by Rule \#2, then we may assume that $v$ has a neighbor $u\in V(G)-V(D)$ which is in a different cluster.
At worst, $v$ has given away $-(k-1)$ charge, which will increase $w'(v)$ by at most that amount.
Lemma \ref{lem:near-verticesKk-3} implies, however, that there are more high-degree neighbors so $v$ has more charge to give.
In this case we have
\[w'(v)\leq\frac{-(k-1)}{4}\cdot\frac{k-7}{2}+k-3+\epsilon+(k-1)=\frac{-1}{8}\left(k^2-24k+39\right)+\epsilon.\]
One can check that for $k\geq23$, this gives $w'(v)\leq-2+\epsilon$.

\begin{case}
Suppose $\deg_G(v)=k-1$ and $v$ is in a cluster of size $r<k-3$ which is adjacent to a vertex of degree $k-1$ which is a key vertex of a gadget or in a $K_{k-3}$ subgraph.
\end{case}
Let $v$ be in a cluster $C_v$ of size $r<k-3$, and let $u$ be an adjacent vertex of degree $k-1$ which is a key vertex of a gadget or in a $K_{k-3}$ subgraph.
Let $u$ be in a different cluster, $C_u$, of size $s$. 
If $s\leq r$ then by Corollary \ref{cor:CloningStructure}, $v$ is a key vertex of a gadget or is in a $K_{k-3}$ subgraph and is covered by Case \ref{case:KeyVertex} or Case \ref{case:Kk-3}.
Thus we may assume that $s>r$.
By Rule \#2, $v$ and each other vertex in $C_v$ receives $-(k-1)/r$ charge from each vertex of $C_u$.
Because $s>r$, the final charge on $v$ is 
\[w'(v)\leq k-3+\epsilon-\frac{k-1}{r}\cdot s<-2+\epsilon.\]
\end{proof}

Note that there was an approximation in Cases \ref{case:KeyVertex} and \ref{case:Kk-3}, where we used $\frac{4}{3}k$ as the degree of a high-degree vertex rather than the actual degree.  If we instead use the precise degree, the equations are more complicated to solve.  Using a CAS one can check that, even without approximating, Lemma \ref{lem:FirstRules} only holds for $k\geq33$.  Therefore, we paid no penalty in strength of argument when we used numbers for which the calculations were easier.

\section{Second stage: averaging charge over the graph}

Now we are done with the first stage of discharging.  The second stage involves global arguments about total charge on $G$.
By Lemma \ref{lem:FirstRules}, we know that the charge on each vertex in $R=V(G)-(L\cup M\cup P\cup Q)$ is at most $-2+\epsilon$. 
However, Rule \#1 also had an effect on the sets $L$ and $M$ because a vertex in one of these special sets could have had neighbors of degree $k+2$ or higher.
A charge of $-\frac{2(k-1)}{k+2}$ (the charge sent by a vertex of degree $k+2$) or less is sent along each edge from a vertex in $R$ to a vertex in $L\cup M$.
We count the number of such edges with the function $e(L\cup M, R)$.
Because vertices of $L$ and $M$ are not adjacent to vertices of degree $k-1$ that are not in the same cluster, Rule \#2 had no effect on any of the four special sets.
Therefore, the total charge on the graph is 
\[\sum_{v\in V(G)}w(v)=\sum_{v\in V(G)}w'(v)\leq \epsilon |V(G)|-2|R|+(k-3)|L|+(k-3)|M|-2|P|\]
\begin{equation}\label{eq:SecondStageCharge}
-(k+1)|Q|-\frac{2(k-1)}{k+2}e(L\cup M,R).
\end{equation}
To further investigate this, we need a bound on the number of edges counted by $e(L\cup M,R)$.
For a vertex $v\in L$ each edge incident with $v$ goes to an edge in either $P\cup Q$ or $R$.
For a vertex $v\in M$ each edge (other than the edge inside the cluster) goes to an edge in either $Q$ or $R$.
It is not possible for there to be an edge from $v\in M$ to $P$ because, by Corollary \ref{cor:CloningStructure}, $v$ would be a structure-vertex and therefore would not belong to $M$.
Using this, it follows that
\begin{equation}\label{eq:BoundOnLuMR}
e(L\cup M,R)=(k-1)|L|-e(L,P\cup Q)+(k-2)|M|-e(M,Q).
\end{equation}

We now combine two bounds on $e(L,P\cup Q)$.  First, we make the simple observation that $e(L,P\cup Q)\leq (k-1)|L|$.
Using Lemma \ref{lem:eLPQ} with the vertex sets $L,P,$ and $Q$ it follows that, for any real numbers $a,b\geq0$ such that $a+b=1$,
\[e(L,P\cup Q)\leq a\left(|L|(k-1)\right)+b\left(2|L|+2|P|+4|Q|\right).\]
By letting $a=\frac{k-4}{2k-2}$ we get
\begin{equation}\label{eq:BoundOnL}
e(L,P\cup Q)\leq\left(\frac{k-4}{2}|L|\right)+\left(\frac{k+2}{k-1}|L|+\frac{k+2}{k-1}|P|+\frac{2(k+2)}{k-1}|Q|\right).
\end{equation}
Also, by Lemma \ref{lem:eMQ} we have that $e(M,Q)\leq3|M|+6|Q|$.
Substituting this and Equation \ref{eq:BoundOnL} into Equation \ref{eq:BoundOnLuMR}, we obtain the following bound on $e(L\cup M,R)$:
\[e(L\cup M,R)\geq \frac{(k+2)(k-3)}{2(k-1)}|L|-\frac{k+2}{k-1}|P|+(k-5)|M|-\frac{8k-2}{k-1}|Q|.\]
Using this we can rewrite Equation \ref{eq:SecondStageCharge} as
\[\sum_{v\in V(G)}w(v)\leq \epsilon|V(G)|-2|R|+(k-3)(|L|+|M|)-2|P|-(k+1)|Q|\]
\[-(k-3)|L|+2|P|-\frac{2(k^2-6k+5)}{k+2}|M|+\frac{16k-4}{k+2}|Q|.\]

This equation simplifies to
\[\sum_{v\in V(G)}w(v)\leq \epsilon|V(G)|-2|R|-\frac{k^2-5k+11}{k+2}|M|-\frac{k^2-15k+6}{k+2}|Q|\]
\[\leq\epsilon|V(G)|-2(|V(G)|-|L|-|P|)\]
because the fractional coefficients on $|M|$ and $|Q|$ are both at least 2.

Recall our assumption that $G$ is a minimal counterexample.
This implies that $\rho(G)>k(k-3)-2(k-1)>0$ and thus
we have $0<\sum_{v\in V(G)}w(v)\leq \epsilon |V(G)|-2|V(G)|+2(|L|+|P|)$.
It follows that 
\[|L|+|P| > |V(G)|\left(1-\frac{\epsilon}{2}\right).\]
This tells us that all but fewer than $n\epsilon/2$ of the vertices in $G$ are in $L$ or $P$.
We will use this information and the potential of $G$ to get lower and upper bounds for $2|E(G)|$.
Note that $2|E(G)|\geq k|P|+(k-1)|L|$, so we get a lower bound
\begin{equation}\label{eq:EGLowerBound}
2|E(G)|> k|V(G)|\left(1-\frac{\epsilon}{2}\right)-|L|.
\end{equation}

Also, $\rho(G)>k(k-3)-2(k-1)>0$ implies that
\begin{equation}\label{eq:EGUpperBound}
2|E(G)|<\left(k-\frac{2}{k-1}+\frac{\epsilon}{k-1}\right)|V(G)|.
\end{equation}

It follows from combining Equations \ref{eq:EGLowerBound} and \ref{eq:EGUpperBound} that
\begin{equation}\label{eq:ContradictKR}
|L|>\frac{|V(G)|}{k-1}\left(2-\epsilon-\frac{\epsilon(k^2-k)}{2}\right).
\end{equation}
This bound on $L$ now allows us to build a new lower bound on $2|E(G)|$ which will lead to a contradiction and complete the proof of Theorem \ref{thm:main}.
Recall that $\text{mic}(G)$ is the maximum of $\sum_{v\in I}\deg_G(v)$ over all independent vertex subsets $I$ of $G$.
The special set $L$ is an independent set of $G$ by construction, and so for a minimal counterexample $G$
it follows that
\[\text{mic}(G)\geq |L|(k-1)>|V(G)|\left(2-\epsilon-\frac{\epsilon(k^2-k)}{2}\right).\]
Using Lemma \ref{lem:KR}, we update the lower bound on $2|E(G)|$ and, on subsequent lines, make a closer comparison of the upper and lower bound.
\[\left(k+\frac{\epsilon-2}{k-1}\right)|V(G)|>2|E(G)|>(k-2)|V(G)|+\text{mic}(G)\]
\[\left(k+\frac{\epsilon-2}{k-1}\right)|V(G)|>|V(G)|\left((k-2)+2-\epsilon-\frac{\epsilon(k^2-k)}{2}\right)\]
\[\frac{\epsilon-2}{k-1}>-\epsilon-\frac{\epsilon(k^2-k)}{2}\]
\[\frac{4}{k^3-2k^2+3k}<\epsilon.\]

Therefore, because $\epsilon\leq\frac{4}{k^3-2k^2+3k}$, these two bounds lead to a contradiction.
This contradiction implies that there is no minimal counterexample $G$ to Theorem \ref{thm:main} which is $k$-critical, not $k$-Ore, and has $\rho(G)>k(k-3)-2(k-1)$.
Therefore, the third statement of Theorem \ref{thm:main} has been proven.
As stated in Section 1, this result gives us a variety of corollaries.
First, we have shown a bound on potential for all $k$-Ore graphs which includes information about subgraphs in the $k$-Ore graphs.
As the size of $k$-Ore graphs grows, the potential goes down by at least $\delta-(k-1)\epsilon\geq0$ for every increase in $k-1$ vertices (which corresponds to an Ore composition with $K_k$).

Second, the graphs which are not $k$-Ore are at least $2(k-1)$ less than $k(k-3)$.
This corresponds to being one edge worth of potential away from the upper bound on potential shown by Kostochka and Yancey \cite{KY2014}.
For $\epsilon=\delta=0$ this proves independently (for the case where $k\geq33$) the result in \cite{KY2015} that the $k$-critical graphs which attain the bound in \cite{KY2014} are exactly the $k$-Ore graphs.

We have also shown that for $k$-critical graphs without $K_{k-2}$ or $K_{k-1}$ subgraphs (for these graphs, $T(G)=0$) that the asymptotic density is above that given by Ore's Conjecture.  That is, where $\overline{f}_k(n)$ is the minimum number of edges in a $(K_{k-2})$-free $k$-critical graph on $n$ vertices, we have shown that
\[\overline{\phi}_k:=\lim_{n\to\infty}\frac{\overline{f}_k(n)}{n} \geq \frac{k}{2}-\frac{1}{k-1}+\frac{\epsilon}{2(k-1)}.\]
