\mychapter{$T_{cs}(G)$, a modification of $T(G)$}



In this chapter, we take a second approach to building a potential function.
This second potential function encodes different information, but still yields a similar overall result for $k$-Ore graphs.
In the new potential function, the $\epsilon$ increase on the coefficient of $|V(G)|$ is paid for with $T_{cs}(G)$ (defined below), which counts structures called \emph{$k$-critical structures}.
Each $k$-critical structure contains either a $K_{k-1}$ or a $K_{k-2}$, so therefore the $\epsilon$ increase can be paid with a much lower cost than the function $T(G)$ used in the previous chapters.

The $k$-Ore graphs are precisely the class of graphs which attain the bound in \cite{KY2014}.
This is proved in \cite{KY2015} and also is independently proved in this work as a corollary to Theorem \ref{thm:main}.
Therefore, $k$-Ore graphs are of particular importance when examining density of edges in a $k$-critical graph and it is worthwhile to obtain a second bound on edge density in $k$-Ore graphs.
Further, this result gives us reason to believe that the $\epsilon$ increase in asymptotic edge density that $\left(K_{k-2}\right)$-free $k$-critical graphs have could be extended to a broader class of $k$-critical graphs.

Before stating the main result of this chapter, we need to establish some terminology.
Let $K_{k-1}^-$ be the complete graph on $k-1$ vertices minus one edge.
%
%
%In this chapter, we obtain many results for $k$-Ore graphs.  Recall that \emph{$k$-Ore graphs} are those that are obtained from $K_k$ and any number of applications of the Ore construction $O(G_1,G_2)$.  The \emph{Ore construction} is a generalization of the Haj\'{o}s construction, and also has similar properties for $k$-critical graphs.  That is, if $G_1$ and $G_2$ are $k$-critical, then so is $O(G_1,G_2)$.  Because $K_k$ is $k$-critical, all $k$-Ore graphs are $k$-critical.  
%
%%first we recall the Ore construction defined in \ref{??} and also $k$-Ore graphs...maybe not
%In fact, $k$-Ore graphs are the class of $k$-critical graphs that attain the Kostochka and Yancey asymptotic bound of $|E(G)|\geq(\frac{k}{2}-\frac{1}{k-1})|V(G)|$.  Therefore, to find structure in the graphs that are close to attaining the Kostochka-Yancey bound, it is natural to start by classifying structure in the $k$-Ore graphs that attain the bound. Our goal is to show that a $k$-critical graph is close to this bound only if it contains a number of disjoint $k$-critical structures, defined below, that is linear with respect to the number of vertices $|V(G)|$.  In this chapter we will first prove it for $k$-Ore graphs.  This is not just an academic exercise; establishing bounds on $k$-Ore graphs will help us better understand reducible configurations in general $k$-critical graphs.
We define a family of graphs $\mathcal{T}$, where $G\in\mathcal{T}$ if and only if
\begin{enumerate}
\item for special vertices $u,v\in V(G)$ the graph $G-\{u,v\}$ is $K_{k-1}^-$,
\item $\deg_G(u)+\deg_G(v)=k-1$,
\item $N_G(u)\cap N_G(v)=\emptyset$,
\item and $\deg_G(v)$ and $\deg_G(u)$ are both at least 2.

\end{enumerate}
Note that if $G$ is a graph in the family $\mathcal{T}$, then when we identify the special vertices $u,v\in V(G)$ we obtain a diamond (Definition \ref{def:Diamond}).

\begin{definition}\label{def:kCritStruc}
Let $G$ be any graph. A subgraph $H\subseteq G$ is a \emph{$k$-critical structure} if either $H=K_{k-1}$, $H=K_k-2K_2$, or $H\in\mathcal{T}$.  We then define $T_{cs}(G)$ to be the maximum number of vertex-disjoint $k$-critical structures in the graph $G$.
\end{definition}

In this chapter, our aim is to prove that there is a linear bound on the number of $k$-critical structures in a $k$-Ore graph.  To do this we will prove the following theorem.
\begin{theorem}\label{thm:Main2}
If $G$ is $k$-Ore and $k\geq4$ then for $a=7(k-1)$ the following is true.
\begin{enumerate}
 \item If $T_{cs}(G)\geq3$ then $T_{cs}(G)-2\geq\frac{|V(G)|-1}{2a}$ and 
 \item if $T_{cs}(G)\leq2$ then $a\geq|V(G)|$.
\end{enumerate}
\end{theorem}


%where can I define 'identify vertices'?


\section{$k$-critical structures}
Recall that a subgraph $D\subseteq G$ is a diamond of $G$ if $D=K_k-uv$ and $\deg_G(x)=k-1$ for each $x\in V(D)-\{u,v\}$.
The vertices $u,v\in V(D)$ are called \emph{endpoints} and we now define the vertices  in $V(D)-\{u,v\}$ to be \emph{interior vertices}.
Note that if $D$ is a diamond of $G$ with endpoints $u,v$, then $G$ is an Ore composition of $K_k$ and $G^*$ for some graph $G^*$.
Further, in the graph $G$, if we delete the interior vertices of $D$ and identify $u$ and $v$ to a single vertex then we obtain a graph that is isomorphic to $G^*$.
We call this process a \emph{vertex-collapse of $D$}, or simply a collapse of $D$.
When we collapse a diamond $D\subseteq G$ with endpoints $u,v$, we will always label the resulting graph $G^*$ and call the single vertex in $V(G^*)-V(G)$ a \emph{fat vertex} and label it $\underline{uv}$.
Also note that for any edge $e\in E(D)$ either $D-e$ contains a $K_{k-1}$, or $D-e=K_k-2K_2$.  Therefore $D-e$ always contains a $k$-critical structure.

We recall what it means to split a vertex, which leads to a definition of another important subgraph called a \emph{$k$-split}.
Given a graph $G$, and a vertex $x\in V(G)$, we can create a new graph $H$ by splitting the vertex $x$.  We split $x$ by deleting it, adding two new vertices $x_1,x_2$, and connecting them to vertices in $V(G)-\{x\}$ so that $N_{H}(x_1)\cup N_{H}(x_2)=N_G(x)$, $N_{H}(x_1)\cap N_{H}(x_2)=\emptyset$, and neither $N_{H}(x_1)$ nor $N_{H}(x_2)$ is empty.  If we identify the vertices $x_1,x_2$ in $H$ the resulting graph is denoted $H/\underline{x_1x_2}$.
Note that $H/\underline{x_1x_2}$ is isomorphic to $G$ if $H$ is constructed as above.
Let $\mathcal{H}$ be the family of graphs obtained from $K_k$ by splitting a vertex $x\in V(K_k)$ such that $x_1$ and $x_2$ both have degree at least 2.  Note that every graph in $\mathcal{H}$ has $k-1$ vertices of degree $k-1$ and two special vertices of degree at most $k-3$.

\begin{definition}
A subgraph $D\subseteq G$ is called a \emph{$k$-split} if $D$ is isomorphic to a graph in $\mathcal{H}$ and $\deg_G(x)=k-1$ for each vertex $x\in V(D)$ with $\deg_D(x)=k-1$.  These vertices are called \emph{interior vertices} of the $k$-split and the two special vertices of degree at most $k-3$ in $D$ we call the \emph{endpoints} of the $k$-split.
\end{definition}
Note that if $D$ is a $k$-split with endpoints $u,v$ in $G$, then $G$ is an Ore composition of $G'$ and $K_k$ for some graph $G'$.
Further, in the graph $G$, if we delete the interior vertices of $D$ and add the edge $uv$ then we obtain a graph that is isomorphic to $G'$.
We call this process an \emph{edge-reduction} of $D$.  The new edge $e$ is called an \emph{edge-replacement} to indicate that it came from an edge-reduction of a $k$-split.  Let $f\in E(D)$ be any edge in a $k$-split.  Then $D-f$ either contains a $K_{k-1}$ or $D-f$ is a graph in the family $\mathcal{T}$.
Therefore $D-f$ always contains a $k$-critical structure.

In the proof of the main result of this chapter, we will make use of graph functions $\theta^*$ and $\theta'$ which we define now.  If $G$ contains $r\geq1$ diamonds, then we label the diamonds $D_1,D_2\ldots,D_r$.  We let $G_1$ be the graph obtained from $G$ by vertex-collapsing $D_1$ with endpoints $u_1,v_1$ to the fat vertex $\underline{u_1v_1}$.  
Suppose that some $D_k$ with $k>1$ was incident to $D_1$ in $G$.  As the interior vertices of a diamond are only adjacent to other vertices of that diamond, these two diamonds must intersect in $G$ at an endpoint.  We may assume that $D_k$ has endpoints $u_1,v_k$ in $G$ for $v_k\neq v_1$.
But in $G_1$ one of the endpoints is now the fat vertex $\underline{u_1v_1}$.  We say that $D_k$ remains intact despite the relabelling of its endpoints.  Therefore, every $D_k$ with $k>1$ is a diamond in $G_1$ and we can vertex-collapse $D_2$ to obtain the graph $G_2$.  At each step, we collapse the diamond with smallest index $D_k$ creating the graph $G_k$, until we reach the end and have obtained the graph $G_r$.  We say that $\theta^*(G)=G_r$; this can be equivalently thought of as collapsing all diamonds in $G$ simultaneously.

If $G$ contains $r\geq1$ $k$-splits, then we label the $k$-splits $D_1,D_2,\ldots,D_r$.  We let $G_1$ be the graph obtained from $G$ by edge-reducing $D_1$.  Because the interior vertices of $D_1$ are only adjacent in $G$ to vertices of $D_1$, every $k$-split $D_k$ with $k>1$ remains intact in $G_1$.  Therefore we can edge-reduce, one at a time, the $k$-split with smallest index $D_k$ creating the graph $G_k$.  At the end of this process, we have obtained the graph $G_r$.  We say that $\theta'(G)=G_r$; this can be equivalently thought of as edge-reducing all $k$-splits in $G$ simultaneously.



\section{Preliminaries}
The following result is the analog of Lemma \ref{lem:TGcompose} and will be needed for the proof of the Theorem \ref{thm:Main2}
\begin{lemma}\label{lem:gluing}
If $G$ is an Ore composition of $G_1$ and $G_2$ then $T_{cs}(G)\geq T_{cs}(G_1)+T_{cs}(G_2)-2$.  Moreover, if $G_1=K_k$ or $G_2=K_k$ then $T_{cs}(G)\geq T_{cs}(G_1)+T_{cs}(G_2)-1$. Lastly, if both $G_1$ and $G_2$ are $K_k$, then $T_{cs}(G)=2$.
\end{lemma}

\begin{proof} 
Suppose that $G$ is an Ore composition of $G_1$ and $G_2$.
Let $e$ be the replaced edge of $G_1$ and $z$ be the split vertex of $G_2$.
From the definition of an Ore composition $T_{cs}(G)\geq T_{cs}(G_1-e)+T_{cs}(G_2-\{z\})$.  
Note that $T_{cs}(G_1-e)\geq T_{cs}(G_1)-1$ and $T_{cs}(G_2-\{z\})\geq T_{cs}(G_2)-1$, because removing a single element can remove at most one $k$-critical structure.
Thus, we get $T_{cs}(G)\geq T_{cs}(G_1)+T_{cs}(G_2)-2$ as desired.  
If $G_1=K_k$ then $T_{cs}(K_k-e)=1$ for every edge $e\in E(G_1)$; also, if $G_2=K_k$ then $T_{cs}(K_k-\{v\})=1$ for every $v\in V(G_2)$.
Thus removing an element from a $K_k$ graph does not remove a $k$-critical structure.
Therefore, it follows that $T_{cs}(G)\geq T_{cs}(G_1)+T_{cs}(G_2)-1$ if either $G_1$ or $G_2$ is $K_k$.
Further, if both $G_1$ and $G_2$ are $K_k$ then $T_{cs}(G)=2$.
\end{proof}



\begin{proposition}\label{prp:TKk1}
Let $G$ be a $k$-Ore graph. Then $T_{cs}(G)\leq1$ if and only if $G=K_k$.
\end{proposition}

\begin{proof}
Note that $T_{cs}(K_k)=1$.  
Now let $G$ be a vertex-minimal $k$-Ore graph where $T_{cs}(G)\leq1$ and $G\neq K_k$.  
Because $G$ is $k$-Ore but not $K_k$, $G$ is an Ore composition of $G_1$ and $G_2$ where $G_1$ and $G_2$ are both $k$-Ore.  By Lemma \ref{lem:gluing} it follows that 
\[1\geq T_{cs}(G)\geq T_{cs}(G_1)+T_{cs}(G_2)-2\]
so $3\geq T_{cs}(G_1)+T_{cs}(G_2).$
Hence $T_{cs}(G_i)\leq1$ for $i=1$ or $i=2$, and by the minimality of $G$ we conclude that $G_i=K_k$.  In this case Lemma \ref{lem:gluing} instead implies that $T_{cs}(G_1)+T_{cs}(G_2)\leq2$ so, in fact, $G_1=G_2=K_k$.  However, in this case $T_{cs}(G)=2$ by Lemma \ref{lem:gluing}.  This contradiction proves the proposition.
\end{proof}



The following lemma is similar to Lemma \ref{lem:kOreAwayFromVertex}, however this lemma covers only $k$-Ore graphs $G$ with $T_{cs}(G)=2$
\begin{lemma}\label{lem:TG2}
If $G$ is $k$-Ore and $T_{cs}(G)=2$ then
\begin{enumerate}
	\item for all $e\in E(G)$ either $T_{cs}(G-e)\geq2$ or there exists a diamond or a $k$-split in $G-e$. 
	\item for all $x\in V(G)$ either $T_{cs}(G-\{x\})\geq2$ or there exists a diamond or a $k$-split in $G-\{x\}$.
\end{enumerate}
\end{lemma}

\begin{proof}
We will prove the lemma by induction on $|V(G)|$.  Let $G$ be a $k$-Ore graph with $T_{cs}(G)=2$ such that all smaller $k$-Ore graphs satisfy the conclusions of the lemma.  Note that $G\neq K_k$ by Proposition \ref{prp:TKk1} because $T_{cs}(G)=2$.  
Thus, $G$ is an Ore composition of two $k$-Ore graphs $G_1$ and $G_2$.  
Let $f\in E(G_1)$ and $y\in V(G_2)$ be the replaced edge of $G_1$ and split vertex of $G_2$, respectively. 
We claim that $T_{cs}(G_i)\leq2$ for $i=1,2$, and prove this claim by contradiction.  Suppose $T_{cs}(G_1)\geq3$.  If $T_{cs}(G_2)\geq2$ then we have by Lemma \ref{lem:gluing} that $2=T_{cs}(G)\geq T_{cs}(G_1)+T_{cs}(G_2)-2\geq3$, which is a contradiction.  If $T_{cs}(G_2)=1$ then $G_2=K_k$ and Lemma \ref{lem:gluing} implies that $2=T_{cs}(G)\geq T_{cs}(G_1)+T_{cs}(G_2)-1\geq3$, which is also a contradiction.  Thus, we conclude that $T_{cs}(G_1)\leq2$.  A similar argument proves that $T_{cs}(G_2)\leq2$ as well.

Now let $e\in E(G)$ from the hypotheses of the lemma be given.  There are two cases, either $e\in E(G_1)$ or $e\in E(G_2)$.  Suppose $e\in E(G_1)$.  For $T_{cs}(G_2)=2$, then by induction $T_{cs}(G_2-\{y\})\geq2$ or there exists a diamond or $k$-split in $G_2-\{y\}$.  Because $G_2-\{y\}\subseteq G-e$, any $k$-critical structures, diamonds, or $k$-splits in $G_2-\{y\}$ also exist in $G-e$ and the lemma holds.  If instead $T_{cs}(G_2)=1$, then the graph $G_2'\subseteq G$ obtained by splitting $G_2$ at the vertex $y$ is a $k$-split.  Removing $e$ from $G$ does not destroy this $k$-split, so there exists a $k$-split in $G-e$.

Now we examine the case where $e\in E(G_2)$.  If $T_{cs}(G_1)=2$ then by induction $T_{cs}(G_1-f)\geq2$ or there exists a diamond or $k$-split in $G_1-f$.  But $G_1-f\subseteq G-e$ because $e\in E(G_2)$, so any $k$-critical structures, diamonds, or $k$-splits in $G_1-f$ also exist in $G-e$ and the lemma holds.  If $T_{cs}(G_1)=1$ then $G_1-f\subseteq G-e$ is a diamond.  Therefore, we have shown that the first statement of the lemma holds in all cases.

We now turn to the second statement.
Let $x\in V(G)$ be given. Suppose $x\in V(G_2)$.  If $T_{cs}(G_1)=2$ then by induction $T_{cs}(G_1-f)\geq2$ or there exists a diamond or $k$-split in $G_1-f$.  But, as before $G_1-f\subseteq G-\{x\}$, so any $k$-critical structures, diamonds, or $k$-splits in $G_1-f$ also exist in $G-\{x\}$ and the lemma holds.  If $T_{cs}(G_1)=1$, then $G_1-f$ is a diamond in $G-\{x\}$.  This case includes the situation where $x$ is an overlap vertex of $G_1$ and $G_2$.

Suppose instead that $x\in V(G_1)-V(G_2)$.  In this case, if $T_{cs}(G_2)=2$ then inductively $T_{cs}(G_2-\{y\})\geq2$ or there exists a diamond or $k$-split in $G_2-\{y\}$, and these structures also exist in $G-\{x\}$ because $G_2-\{y\}\subseteq G-\{x\}$.  If $T_{cs}(G_2)=1$, then the graph $G_2'$ obtained by splitting $G_2$ at the vertex $y$ is a $k$-split.  Because $x\notin V(G_2)$, this $k$-split $G_2'$ will be intact after removing the vertex $x$ from $G$.  This completes the proof of the lemma.
\end{proof}

For the following proposition we show that that to obtain a smaller $k$-Ore graph, a diamond can be vertex-collapsed and a $k$-split can be edge-reduced.
\begin{proposition}\label{prp:G'Ore}
Suppose that $G$ is $k$-Ore.  If $G$ contains a diamond $D$ then the graph $G^*$ obtained by vertex-collapsing $D$ is also $k$-Ore.  If $G$ contains a $k$-split $D$ then the graph $G'$ obtained by edge-reducing $D$ is $k$-Ore.  
\end{proposition}

\begin{proof}
Suppose that neither statement of the proposition holds.  Then let $G$ be a counterexample with a minimum number of vertices; note that $G\neq K_k$ as this has no diamonds or $k$-splits.  Thus, we have that $G$ is an Ore composition of two $k$-Ore graphs $G_1$ and $G_2$.

Suppose that $D$ is a diamond of $G$.
Then we consider the graph $H$ where $G$ is an Ore composition of $K_k$ and $H$ with overlap vertices which are the endpoints of $D\subseteq G$.  Note that $H$ is the graph $G^*$ in the statement of the proposition, so it remains to prove that $H$ is $k$-Ore.
Note that $D$ must be a diamond of $G_1$ or $G_2$; assume for now that $D$ is a diamond of $G_1$.
By the minimality of $G$ it follows that $G_1$ is an Ore composition of $K_k$ and $G'_1$ where $G'_1$ is a $k$-Ore graph.
But now we can realize $H$ as an Ore composition of $G'_1$ and $G_2$, both of which are $k$-Ore; therefore, $H$ is $k$-Ore.
The method of argument when $D$ is a diamond of $G_2$ is identical.

Now suppose that $D\subseteq G$ is a $k$-split.  The $k$-split $D$ must be a subgraph of $G_1$ or $G_2$; assume $D\subseteq G_1$.
 Further, $G$ is also an Ore composition of $H$ and $K_k$ with overlap vertices which are the endpoints of $D$.
By the minimality of $G$ it follows that $G_1$ is an Ore composition of $G^*_1$ and $K_k$ where $G^*_1$ is $k$-Ore.
Now $H$ is a Ore composition of $G^*_1$ and $G_2$, both of which are $k$-Ore; therefore, $H$ is $k$-Ore.
The method of argument when $D\subseteq G_2$ is identical.
\end{proof}



\section{Main result on $k$-Ore graphs}
Here we restate and then prove the main result of this chapter.  This proof is broken up into 10 claims.
%and the finishing stuff, which will not be here
\addtocounter{theorem}{-6}
%!!!count chapter2's theorems
\begin{theorem}
If $G$ is $k$-Ore and $k\geq4$ then for $a=7(k-1)$ the following is true.
\begin{itemize}
 \item If $T_{cs}(G)\geq3$ then $T_{cs}(G)-2\geq\frac{|V(G)|-1}{2a}$ and 
 \item if $T_{cs}(G)\leq2$ then $a\geq|V(G)|$.
\end{itemize}
\end{theorem}
\addtocounter{theorem}{5}

\begin{proof}
Suppose the theorem does not hold.  Then let $G$ be a counterexample with a minimum number of vertices.  That is, let $G$ be a $k$-Ore graph where either $T_{cs}(G)\geq3$ and $T_{cs}(G)-2<\frac{|V(G)|-1}{2a}$ or $T_{cs}(G)\leq2$ and $a<|V(G)|$, and let any $k$-Ore graph with fewer vertices than $G$ follow the inequalities of Theorem \ref{thm:Main2}.  By Proposition \ref{prp:TKk1}, we may assume that $G\neq K_k$ and $T_{cs}(G)\geq2$.  Therefore $G$ is an Ore composition of two $k$-Ore graphs $G_1$ and $G_2$.
Note that $G_1$ and $G_2$ follow the inequalities of \ref{thm:Main2}.

%%%%%%%%%%%%%%%%
\begin{claim}\label{clm:DiamDisjoint} 
No two diamonds are incident in $G$.
\end{claim}

\begin{proof} 
Suppose two diamonds $D,D'$ are incident in $G$.  Note that two distinct diamonds could only intersect at their endpoint vertices; thus, we say that $D$ has endpoints $u,v$ and that $D'$ has endpoints $v,w$.  Collapsing $D$ into a fat vertex $\underline{uv}$ still leaves $D'$ intact, although the endpoint $v\in V(D')$ is now the fat vertex $\underline{uv}$. We can collapse this diamond as well.  Then both diamonds have collapsed into a single fat vertex $\underline{uvw}$, and we have a new graph $G'$ which has $2(k-1)$ fewer vertices than $G$.  
%%%%%%%%ADD CASE WHERE 1 COLLAPSE GIVES A Kk  12/6

By Proposition \ref{prp:G'Ore}, $G'$ is $k$-Ore, so by the minimality of $G$, Theorem \ref{thm:Main2} applies to $G'$.  We can recover $G$ from $G'$ by expanding the fat vertex back into two diamonds, one at a time.  By doing this we have possibly removed a $k$-critical structure in $G'$ which was using the vertex $\underline{uvw}$; however, we have also introduced	two $K_{k-1}$ subgraphs, namely $D-\{v\}$ and $D'-\{v\}$.
Therefore, if $t=T_{cs}(G')$ it follows that 
\begin{equation}\label{eq:case1}
T_{cs}(G)\geq t+1.
\end{equation}

If $G'=K_k$ then, in fact, we can ensure that the fat vertex is not in a $k$-critical structure and expanding the fat 
vertex into two adjacent diamonds adds two $k$-critical structures while removing none. 
Therefore we have $T_{cs}(G)=3$ and $|V(G)|=3k-2$.
By supposition we have that $T_{cs}(G)-2<\frac{|V(G)|-1}{2a}$, but because this requires $2a<3(k-1)$, we have a contradiction, so $G'\neq K_k$.

Therefore, Proposition \ref{prp:TKk1} implies that $T_{cs}(G')\geq2$, so $T_{cs}(G)\geq3$ by Equation \ref{eq:case1}. If $T_{cs}(G')=2$, then by the minimality of $G$ we have that $|V(G')|\leq a$.  But then $1\leq (T_{cs}(G')+1)-2\leq T_{cs}(G)-2$ and because $G$ is 
a counterexample, we have 
\[1\leq T_{cs}(G)-2<\frac{|V(G)|-1}{2a}=\frac{|V(G')|+2k-3}{2a}\leq\frac{a+2k-3}{2a}.\]
This implies that $a<2k-3$, which is a contradiction.

Now we assume that $T_{cs}(G')\geq3$.  Then by the minimality of $G$ we have $T_{cs}(G')-2\geq\frac{|V(G')|-1}{2a}$.  Because $2a\geq2(k-1)$ and $G$ has $2(k-1)$ more vertices than $G'$ it follows that
\[T_{cs}(G)-2\geq T_{cs}(G')-1\geq\frac{|V(G')|-1}{2a}+1\geq\frac{|V(G')|+2(k-1)-1}{2a}\]
\[=\frac{|V(G)|-1}{2a}.\]
Thus $G$ is not a counterexample at all.  Therefore we have proven that two diamonds are not incident in $G$.
\end{proof}




We now consider $\theta^*(G)$, which is obtained by taking all diamonds in $G$ and simultaneously collapsing them.  By Claim \ref{clm:DiamDisjoint}, we know that any
vertex in $\theta^*(G)$ corresponds either to a single vertex in $G$, or a single
diamond in $G$.  By repeated applications of Proposition \ref{prp:G'Ore} we can show that $\theta^*(G)$ is $k$-Ore.

\begin{claim} 
$\theta^*(G)\neq K_k$.
\end{claim}

\begin{proof}
Suppose, for sake of contradiction, that $\theta^*(G)=K_k$.  If $T_{cs}(G)=2$ then $G$ can have at most two
diamonds.  In this case $|V(G)|\leq 3k-2$ so $G$ is not a counterexample at all.  Therefore we may assume that $T_{cs}(G)\geq3$.

Let $\ell$ be the number of vertices in $\theta^*(G)$ which are fat vertices.  If $\ell=1$, then $G$ is an Ore composition of $K_k$ and $K_k$ and $T_{cs}(G)=2$.  So we may assume that $\ell\geq2$.  Suppose $\ell=2$.  Then we have that $1\leq T_{cs}(G)-2<\frac{|V(G)|-1}{2a}$.  But $|V(G)|=3k-2$ and $2a\geq 3(k-1)$, so this is a contradiction.

Therefore, we can assume that $\ell\geq3$.  Then $T_{cs}(G)\geq\ell$ and $|V(G)|=k-\ell+k\ell=(\ell+1)k-\ell$.  Because $a\geq3k-3$ we have
\[\ell-2\leq T_{cs}(G)-2<\frac{|V(G)|-1}{2a}=\frac{(\ell+1)(k-1)}{2a}\leq
\frac{(\ell+1)(k-1)}{2\cdot3(k-1)}=\frac{\ell+1}{6}.\]
For $\ell\geq3$ this inequality is a contradiction.  Therefore, we have proven that $\theta^*(G)\neq K_k$.
\end{proof}

\begin{claim}\label{clm:superdiamond}
If $D\subseteq\theta^*(G)$ is a diamond then at most one vertex of $D$ is a diamond in $G$.  That is, at most one vertex of $D$ is a 
fat vertex.  Furthermore, this vertex can only be an interior vertex.
\end{claim}
%%%%%%12/6 THERE IS A PROBLEM IN THIS PROOF WHEN G''\neq K_k

%%%%later:  we never use the graph G'...do I need to define it?
\begin{proof}
Suppose that there is a diamond $D\subseteq\theta^*(G)$ where $\ell\geq2$ vertices of $D$ are fat vertices, meaning they were diamonds in $G$.  We
replace each fat vertex of $D$ with a diamond to recover the subgraph $\widehat{D}\subseteq G$ which can be vertex-collapsed to $D$; that is, $\theta^*(\widehat{D})=D$.
Further, let $\theta^*(D)=\underline{x}$. Let $G'$ denote the graph obtained from $G$ by collapsing $\widehat{D}$ to $D$, and let
$G''$ denote the graph obtained from $G'$ by collapsing $D$ to $\underline{x}$.

Suppose $G''=K_k$.  Then $T_{cs}(G'')=1$ and $T_{cs}(G)\geq\ell+1\geq3$, because when we replace
$\underline{x}$ with $\widehat{D}$ we leave a $K_{k-1}\subseteq G-\widehat{D}$ intact, and we add $\ell$ new $K_{k-1}$ subgraphs from the diamonds in
$\widehat{D}$.  We also have $|V(G)|=k+(k-1)+\ell(k-1)=(\ell+2)(k-1)+1$.  Because $G$ is a counterexample with $T_{cs}(G)\geq3$ we have $T_{cs}(G)-2<\frac{|V(G)|-1}{2a}$.
This gives us the string of inequalities
\[\ell-1\leq T_{cs}(G)-2<\frac{|V(G)|-1}{2a}=\frac{(\ell+2)(k-1)}{2a}.\]
This implies that $a<\frac{\ell+2}{2\ell-2}(k-1)$, which has a maximum value (when $\ell=2$) of 2.  But $a\geq2(k-1)$, so this is a contradiction and $G''$ cannot be $K_k$.

Thus, we may assume that $T_{cs}(G'')\geq2$.  If $T_{cs}(G'')=2$ then by the minimality of $G$ it follows that $|V(G'')|\leq a$, so $|V(G)|\leq a+3(k-1)$.  Then we have 
\begin{equation}\label{eq:superdiamond1}
1\leq T_{cs}(G)-2<\frac{|V(G)|-1}{2a}\leq\frac{a+3k-4}{2a}.
\end{equation}
This implies that $a<3k-4$, which is a contradiction.  If $T_{cs}(G'')\geq3$ then by 
the minimality of $G$ it follows that $T_{cs}(G'')-2\geq\frac{|V(G'')|-1}{2a}$.  Also, $T_{cs}(G'')+1\leq T_{cs}(G)$, because
if we replace $\underline{x}$ with $\widehat{D}$, we 
possibly destroy one $k$-critical structure that contained $\underline{x}$, but we 
add at least two $K_{k-1}$ subgraphs from the diamonds of $\widehat{D}$. Now we have
\begin{equation}\label{eq:superdiamond2}
\frac{|V(G)|-1}{2a}>T_{cs}(G)-2\geq T_{cs}(G'')-1\geq\frac{|V(G'')|-1}{2a}+1,
\end{equation}
which implies that $|V(G)|>|V(G'')|+2a$.  But $|V(G'')|+3(k-1)\geq |V(G)|$ and it follows that
 $3(k-1)>2a$, which is a contradiction. Therefore, there is no diamond $D\subseteq\theta^*(G)$ with more than one fat vertex.

Now we suppose that one the endpoints of the diamond $D\subseteq\theta^*(G)$ is a fat vertex. Then $T_{cs}(\widehat{D})=2$, and $T_{cs}(G'')+1\leq T_{cs}(G)$ because replacing
$\underline{x}$ with $\widehat{D}$ may remove one $k$-critical structure, but also will add the two $k$-critical structures in $\widehat{D}$.  If $G''=K_k$, then $T_{cs}(G)=T_{cs}(\widehat{D})+1=3$ because the $K_{k-1}$ of $K_k-\{\underline{x}\}$ remains intact.  Also $|V(G)|=3k-2$. 
But this implies that $1<\frac{3(k-1)}{2a}$, which is a contradiction.  So we may assume that $G''\neq K_k$.  As $T_{cs}(G)\geq T_{cs}(G'')+1$, it follows from Proposition \ref{prp:TKk1} that $T_{cs}(G)\geq3$.  Because of this and the fact that $|V(G)|=|V(G'')|+2(k-1)<|V(G'')|+3(k-1)$, we have the same hypotheses that led to the contradictory Equations \ref{eq:superdiamond1} and \ref{eq:superdiamond2}.
\end{proof}

In fact, each diamond $D$ in $\theta^*(G)$ has exactly one fat vertex.  
If any diamond in $D\subseteq\theta^*(G)$ had no fat vertices, then $D\subseteq G$ so would
have been collapsed to a vertex in $\theta^*(G)$. 
When we expand the fat vertex of $D\subseteq\theta^*(G)$ and recover $\widehat{D}\subseteq G$, we define this structure to be a \emph{super-diamond}.  Using this language, we say that each diamond in $\theta^*(G)$ comes from a super-diamond in $G$.
\begin{claim}\label{clm:SupDiamDisjoint}
No two diamonds intersect in $\theta^*(G)$.
\end{claim}
\begin{proof}
Let $D_1,D_2$ be two diamonds in $\theta^*(G)$ whose vertex sets intersect.  Note that the diamonds can only share endpoints, so we may assume that $D_1$ has endpoints $u,v$ and that $D_2$ has endpoints $v,w$.  We collapse $D_1$ to a fat vertex $\underline{uv}$; by Proposition \ref{prp:G'Ore}, the resulting graph $H$
 is $k$-Ore, and either $D_2$ is a diamond in $G^*$ with endpoints $\underline{uv},w$, or $H$ is $K_k$.
 
First suppose that $H$ is $K_k$.  Then $T_{cs}(\theta^*(G))=2$, and $|V(\theta^*(G))|=2k-1$.  By Claim \ref{clm:superdiamond} each diamond in $\theta^*(G)$ has exactly one fat vertex, and they do not overlap.  Thus, $|V(G)|=4k-3$.  If $T_{cs}(G)=2$, then $|V(G)|=4k-3\leq a$ is a contradiction. 
If $T_{cs}(G)\geq3$ then $1\leq T_{cs}(G)-2<\frac{4k-4}{2a}$ implies that $a<2(k-1)$, which is also a contradiction.  Therefore, we can assume that $H$ is not $K_k$.  Then by Proposition \ref{prp:G'Ore}, when we collapse $D_2\subseteq H$ so that we get the single fat vertex $\underline{uvw}$, the resulting graph will be $k$-Ore.

Now let $C=D_1\cup D_2$ 
%%%%don't use greek letters except on diamonds/k-splits
be the subgraph of $\theta^*(G)$ that consists of both diamonds; $T_{cs}(C)=2$.  We can replace each fat vertex in $C$ with a diamond in order to recover $\widehat{C}\subseteq G$.  Note that $\theta^*(\widehat{C})=C$ so $T_{cs}(\widehat{C})\geq2$, and that $C$ can collapse further to $\underline{uvw}$ as above.  Let $G'$ be the graph obtained from $G$ by collapsing $\widehat{C}\subseteq G$ to $C$, and let $G''$ be the graph obtained from $G'$ by collapsing $C$ to $\underline{uvw}$.  Then $|V(G)|=|V(G'')|+4(k-1)$.  If $G''$ is $K_k$, then $T_{cs}(G)\geq3$, because $G''-\{\underline{uvw}\}$ is a $K_{k-1}$ that remains intact when we substitute $\widehat{C}$ for the fat vertex.  So $1\leq T_{cs}(G)-2<\frac{|V(G)|-1}{2a}$ implies that $2a<|V(G)|-1=5(k-1)$, which is a contradiction.  Therefore we may assume that $G''$ is not $K_k$.  Then $T_{cs}(G)\geq T_{cs}(G'')+1$ because replacing $\underline{uvw}$ with $\widehat{C}$ possibly removes a $k$-critical structure in $G''$ but adds at least 2 from $\widehat{C}$, and by Proposition \ref{prp:TKk1} $T_{cs}(G'')\geq2$ which gives $T_{cs}(G)\geq3$.  But then
\[\frac{|V(G)|-1}{2a}>|T_{cs}(G)|-2\geq T_{cs}(G'')-1\geq\frac{|V(G'')|-1}{2a}+1\]
implies that $|V(G)|>|V(G'')|+2a$, meaning that $4(k-1)>2a$, and this is a contradiction.

Thus, we have shown that no such diamonds $D_1,D_2$ can exist in $\theta^*(G)$.
\end{proof}


We now consider $\theta^*(\theta^*(G))$
%%% should I call this \theta^{**}?
, which is obtained by taking all diamonds in $\theta^*(G)$ and simultaneously collapsing them.  By Claims \ref{clm:DiamDisjoint} and \ref{clm:SupDiamDisjoint}, we know that every vertex in $\theta^*(\theta^*(G))$ corresponds to either a single vertex in $G$, a single diamond in $G$, or a single super-diamond in $G$.


%%%%%%%%%%%
\begin{claim}\label{**GnotKk}
$\theta^*(\theta^*(G))$ is not $K_k$.
\end{claim}
\begin{proof}
Suppose, for sake of contradiction, that $\theta^*(\theta^*(G))=K_k$.  First suppose that $T_{cs}(G)=2$.  Since $T_{cs}(G)\geq T_{cs}(\theta^*(G))$ it follows that $\theta^*(G)$ can have at most two diamonds.  Thus
$|V(\theta^*(G))|\leq3k-2$ and $|V(G)|\leq5k-4$, which is a contradiction as $a>5k-4$.

Therefore, we may assume that $T_{cs}(G)\geq3$.  Let $\ell$ be the number of diamonds in $\theta^*(G)$. Then $|V(G)|\geq k+2\ell(k-1)=(2\ell+1)(k-1)+1$ because each diamond in $\theta^*(G)$ 
is a super-diamond in $G$ by Claim \ref{clm:superdiamond}.  If $\ell\leq2$ then
we have $1\leq T_{cs}(G)-2<\frac{|V(G)|-1}{2a}\leq\frac{5(k-1)}{2a}$ which is a contradiction as $a>5(k-1)$.  If $\ell\geq3$, then because each diamond in $\theta^*(G)$ corresponds to a super-diamond in $G$ and each super-diamond contains a $k$-critical structure, we have $T_{cs}(G)\geq\ell$.  But $a>4(k-1)$ so it follows that
\[\ell-2\leq T_{cs}(G)-2<\frac{|V(G)|-1}{2a}\leq\frac{(2\ell+1)(k-1)}{2a}\leq\frac{(2\ell+1)(k-1)}{2\cdot4(k-1)}\]
\[=\frac{2\ell+1}{8}.\]
For $\ell\geq3$, this inequality is a contradiction.  Therefore, we have shown that $\theta^*(\theta^*(G))\neq K_k$.
\end{proof}

\begin{claim}\label{clm:**GnoDiamond}
There are no diamonds in $\theta^*(\theta^*(G))$.
\end{claim}
\begin{proof}
Let $D\subseteq\theta^*(\theta^*(G))$ be a diamond with endpoints $u,v$.  Replace each fat vertex with either a super-diamond or diamond so that we recover $\widehat{D}\subseteq G$ and $\theta^*(\theta^*(\widehat{D}))=D$.  Note that $D$ must have at least one fat vertex that corresponds to a super-diamond in $G$, otherwise $\theta^*(\theta^*(\widehat{D}))$ would be a single fat vertex instead of a diamond.  Let $G'$ be the graph obtained from $G$ by collapsing $\widehat{D}$ to $D$, and let $G''$ be the graph obtained from $G'$ by further collapsing $D$ to a fat vertex $\underline{uv}$.  Let $\ell$ be the number of fat vertices in $D$; as noted above, $\ell\geq1$.  Also, $|V(G)|\leq|V(G'')|+(2\ell+1)(k-1)$. 

Suppose first that $\ell\geq2$. Then $T_{cs}(D)\geq\ell$.  When we replace $\underline{uv}$ with $\widehat{D}$, we lose at most one $k$-critical
structure in $G''$, but gain at least $\ell$ structures from $\widehat{D}$.  Thus $T_{cs}(G)\geq T_{cs}(G'')+\ell-1$.  As long as $T_{cs}(G'')\geq2$, this implies that $T_{cs}(G)\geq3$. Otherwise, if $G''=K_k$, then we lose no structures when expanding $\underline{uv}$, as $G''-\{\underline{uv}\}=K_{k-1}$.  So in that case $T_{cs}(G)\geq T_{cs}(G'')+\ell\geq3$.  In all cases $T_{cs}(G)\geq3$ and thus it follows that $T_{cs}(G)-2<\frac{|V(G)|-1}{2a}$.

If $T_{cs}(G'')\leq2$ then $T_{cs}(G)-2\geq\ell-1$ and $|V(G'')|\leq a$.  From these observations, it follows that 
\[\ell-1\leq T_{cs}(G)-2<\frac{|V(G)|-1}{2a}<\frac{|V(G)|}{2a}\leq\frac{a+(2\ell+1)(k-1)}{2a}\]
\[=\frac{1}{2}+\frac{(2\ell+1)(k-1)}{2a}.\]
But this implies that $a<\frac{2\ell+1}{2\ell-3}(k-1)$.  When $\ell\geq2$ it follows that $a<5(k-1)$, but this is a contradiction.

Thus we may assume that $T_{cs}(G'')\geq3$.  In this case, 
\[\frac{|V(G)|-1}{2a}>T_{cs}(G)-2\geq T_{cs}(G'')+\ell-3\geq\frac{|V(G'')|-1}{2a}+\ell-1\]
which implies that $|V(G)|>|V(G'')|+2a(\ell-1)$.  But we know that with $\ell$ fat vertices in $D$, $|V(G'')|+(2\ell+1)(k-1)\geq|V(G)|$.  Combining these two inequalities, we get $(2\ell+1)(k-1)>2a(\ell-1)$, which can be written as $\frac{2\ell+1}{\ell-1}(k-1)>2a$.  Because $\frac{2\ell+1}{\ell-1}$ is a decreasing function for $\ell\geq2$, we have $5(k-1)>2a$, which is a contradiction.

We now suppose that $\ell=1$.  In this case, the fat vertex $\underline{x}\in V(D)$ must correspond to a super-diamond $C\subseteq G$.  Note that $C\subseteq\widehat{D}$.  Also note that a super-diamond contains a $K_{k-1}$ that does not intersect either endpoint of the super-diamond.  Thus the vertices $V(D)-\{\underline{x}\}$ either form a $K_{k-1}$ or form a graph in $\mathcal{T}$ that uses the endpoints of $C$ as well.  Either way $T_{cs}(\widehat{D})=2$ and thus $T_{cs}(G)\geq3$.

If $T_{cs}(G'')\leq2$ then $|V(G'')|\leq a$ by the minimality of $G$.  By hypothesis, $1\leq T_{cs}(G)-2<\frac{|V(G)|-1}{2a}$ and so $2a<|V(G)|-1$.  But $|V(G)|\leq|V(G'')|+3(k-1)\leq a+3(k-1)$ so this implies that $a<3k-4$, which is a contradiction.

If $T_{cs}(G'')\geq3$ then by the minimality of $G$, $T_{cs}(G'')-2\geq\frac{|V(G'')|-1}{2a}$.  So then
\[\frac{|V(G)|-1}{2a}>T_{cs}(G)-2\geq T_{cs}(G'')-1\geq\frac{|V(G'')|-1}{2a}+1.\]
This implies that $|V(G)|>|V(G'')+2a$, but we also have $|V(G'')|+3(k-1)\geq|V(G)|$ so then $3(k-1)>2a$, which is a contradiction.

Therefore we have shown that $\theta^*(\theta^*(G))$ has no diamonds.
\end{proof}



\begin{claim}\label{clm:fatvtxsplit}
If $D\subseteq \theta^*(\theta^*(G))$ is a $k$-split then no more than one vertex of $D$ comes
from a diamond or super-diamond.
\end{claim}
%furthermore, we want to show that this fat vertex can't be an endpoint.!!! Also, both interior.
\begin{proof}
Suppose that $D$ is a $k$-split with endpoints $u,v$ where $\ell\geq2$ vertices of $D$ are fat vertices.  We replace each fat vertex of $D$ with a diamond or super-diamond to recover $\widehat{D}\subseteq G$, where $\theta^*(\theta^*(\widehat{D}))=D$.  We can also edge-reduce $D$ to an edge-replacement $e=uv$ by adding the edge $e=uv$ and deleting all interior vertices.  Let $G'$ be the graph obtained from $G$ by collapsing $\widehat{D}$ to $D$ and let $G''$ be the graph obtained from $G'$ by edge-reducing $D$ to $e$.  Replacing an edge-replacement with a $k$-split adds $k-1$ vertices to a graph, and replacing a fat vertex with a diamond or super-diamond adds at most $(2k-2)$ vertices to a graph.  Then $|V(G)|\leq|V(G'')|+(2\ell+1)(k-1)$.  We claim that $T_{cs}(G)\geq3$, and to show this we inspect three cases when $T(G'')\geq2$, and then show how their conclusions are stronger for $G''=K_k$.
\addtocounter{case}{-5}
%!!!check this counter!
\begin{case}\label{cse:l3+}
Suppose $\ell\geq3$
\end{case}
When we replace the edge-replacement $e=uv$ with $\widehat{D}$ we lose at most two $k$-critical structures in $G''$ because $u$ and $v$ may be fat vertices that are also in $k$-critical structures in $G''$.  However, we gain at least $\ell\geq3$ $k$-critical structures in $\widehat{D}$.  Therefore $T_{cs}(G)\geq T_{cs}(G'')-2+\ell$.

\begin{case}\label{cse:l2ends}
Suppose $\ell=2$ and both fat vertices are endpoints of $D$.
\end{case}
When we replace the edge-replacement $e$ with $\widehat{D}$, we lose at most two structures.  However, as $D-\{u,v\}=K_{k-1}$, this $k$-critical structure remains when $u,v$ are replaced with diamonds and it follows that $T_{cs}(\widehat{D})\geq3$.  Therefore $T_{cs}(G)\geq T_{cs}(G'')-2+3=T_{cs}(G'')+1$.

\begin{case}\label{cse:l2center}
Suppose $\ell=2$ and at least one fat vertex in $D$ is an interior vertex.
\end{case}
We replace the edge-replacement $e\in E(G'')$ with $\widehat{D}$.  If $e$ is in a $k$-critical structure in $G''$ then we lose that $k$-critical structure, but we gain at least $\ell$ $k$-critical structures in $\widehat{D}$.  Hence, $T_{cs}(G)\geq T_{cs}(G'')-1+\ell$.  Otherwise, $e\in E(G'')$ is not in a $k$-critical structure, and we lose at most one $k$-critical structure, as one of the endpoints of $e$ may be a fat vertex that is split in $\widehat{D}$.  However, we gain at least $\ell$ $k$-critical structures in $\widehat{D}$, so here as well $T_{cs}(G)\geq T_{cs}(G'')-1+\ell$.  Therefore we always have $T_{cs}(G)\geq T_{cs}(G'')+1$ when $T_{cs}(G'')\geq2$.

Now consider when $G''=K_k$.  We can lose at most one structure in $G''$ since only one exists.  Therefore, in Case \ref{cse:l3+} we have $T_{cs}(G)\geq T_{cs}(G'')-1+\ell\geq3$.  In Case \ref{cse:l2ends}, we have $T_{cs}(G)\geq T_{cs}(G'')-1+3\geq3$.  And in Case \ref{cse:l2center} only one endpoint of $D$ can be a fat vertex.  Without loss of generality let it be $v$.  Then $G''-\{v\}=K_{k-1}$ remains intact in $G$ so $T_{cs}(G)\geq T_{cs}(G'')+2=3$.

Now we have shown the claim that $T_{cs}(G)\geq3$ and will show contradictions regardless of whether $T_{cs}(G'')\leq2$ or $T_{cs}(G'')\geq3$.
Suppose first that $T_{cs}(G'')\leq2$. By the minimality of $G$ it follows that $|V(G'')|\leq a$.  Now if $\ell=2$ then $|V(G)|\leq a+5(k-1)$.  But then it follows that
\[1\leq T_{cs}(G)-2<\frac{|V(G)|-1}{2a}\leq\frac{a+5k-6}{2a}\]
and this implies that $a<5k-6$ which is a contradiction.  Therefore we may assume that $\ell\geq3$.  Then the argument of Case \ref{cse:l3+} implies that $T_{cs}(G)\geq\ell$ so
\[\ell-2\leq T_{cs}(G)-2<\frac{|V(G)|-1}{2a}\leq\frac{a+(2\ell+1)(k-1)-1}{2a}\]
\[<\frac{1}{2}+\frac{(2\ell+1)(k-1)}{2a}.\]
It follows that $\ell-\frac{5}{2}<\frac{(2\ell+1)(k-1)}{2a}$ and thus $a<\frac{2\ell+1}{2\ell-5}(k-1)$.  
But $\frac{2\ell+1}{2\ell-5}$ is a decreasing function on $\ell\geq3$ with a maximum at $\ell=3$.  Therefore we have shown that $a<7(k-1)$, which is a contradiction.

Now suppose instead that $T_{cs}(G'')\geq3$. Then by the minimality of $G$ it follows that $T_{cs}(G'')-2\geq\frac{|V(G'')|-1}{2a}$.  If $\ell=2$ then
\[\frac{|V(G)|-1}{2a}>T_{cs}(G)-2\geq T_{cs}(G'')-1\geq\frac{|V(G'')|-1}{2a}+1\]
which implies that $|V(G)|>|V(G'')|+2a$.  However, $|V(G'')|+5(k-1)\geq V(G'')$ so we have shown that $5(k-1)>2a$, which is a contradiction.  Therefore we may assume that $\ell\geq3$.  Then from Case \ref{cse:l3+} it follows that
\[\frac{|V(G)|-1}{2a}>T_{cs}(G)-2\geq T_{cs}(G'')-4+\ell\geq\frac{|V(G'')|-1}{2a}+\ell-2.\]
This implies that $|V(G)|>|V(G'')|+2a(\ell-2)$.  But $|V(G'')|+(2\ell+1)(k-1)\geq|V(G)|$ so together these inequalities show that $\frac{2\ell+1}{\ell-2}(k-1)>2a$.  When $\ell\geq3$ this implies that $7(k-1)>2a$, which is a contradiction.

Therefore, we have shown that any $k$-split $D\in\theta^*(\theta^*(G))$ has at most one fat vertex.

%[I NEED TO ADD A PIECE ABOUT HOW THIS ONLY OCCURS AT AN INTERIOR VERTEX AS WELL]

\end{proof}

\begin{claim}\label{clm:ksplitsdisjoint}
No two $k$-splits are incident in $\theta^*(\theta^*(G))$.
%%%%%12/6 WE MIGHT CHANGE 'ARE INCIDENT' FOR 'INTERSECT'
\end{claim}
\begin{proof}
Suppose that $D_1,D_2$ are $k$-splits in $\theta^*(\theta^*(G))$ with endpoints $u,v$ and $v,w$ respectively.  By Claim \ref{clm:fatvtxsplit} it follows that each of $D_1$ and $D_2$ has at most one fat vertex.  Also, these fat vertices are disjoint, as they must be interior vertices.
We can edge-reduce $D_1$ to a edge-replacement $e=uv$ and by Proposition \ref{prp:G'Ore} the resulting graph $H$ is $k$-Ore.  Also, $H\neq K_k$ as $D_2\subseteq H$ has $k+1$ vertices. Then we edge-reduce $D_2$ to a edge-replacement $f=vw$.

Let $C=D_1\cup D_2$ be the subgraph of $\theta^*(\theta^*(G))$ that consists of both $k$-splits.  $T_{cs}(C)=2$.  If there are fat vertices in $C$, then we replace them with a diamond or super-diamond to recover $\widehat{C}\subseteq G$, and it follows that $T_{cs}(\widehat{C})\geq2$. 
%%%%%%actually, it's equal to 2
 Note that $\widehat{C}=C$ is possible.  Let $G'$ be the graph obtained from $G$ by collapsing $\widehat{C}$ to $C$ and let $G''$ be the graph obtained from $G'$ by edge-reducing $D_1\subseteq C$ to $e=uv$ and $D_2\subseteq C$ to $f=vw$.

When we replace $e$ with $D_1$ we gain a $k$-critical structure overall unless the edge $e$ is used in a $k$-critical structure of $G''$.  Similarly, replacing $f$ with $D_2$ gains a $k$-critical structure overall unless the edge $f$ is used in a $k$-critical structure of $G''$.  But if $e,f$ are both used in a $k$-critical structure, then they are part of the same $k$-critical structure because they are incident at the vertex $v$ and $k$-critical structures are disjoint.  So when we expand the edge-replacements $e,f$ we lose at most one structure, and gain $T_{cs}(C)=2$.  Thus $T_{cs}(G)\geq T_{cs}(G')\geq T_{cs}(G'')+1$ because $T_{cs}(\widehat{C})\geq T_{cs}(C)$.
%%%%%show a little earlier that |V(G)|\leq|V(G'')|+6(k-1)


Suppose first that $G''=K_k$.  Then $|V(G')|=k+2(k-1)=3k-2$ and $|V(G)|\leq3k-2+2(2k-2)=7k-6$ because each $k$-split in $G'$ may have one fat vertex that was a super-diamond in $G$.  But $G''-\{v\}=K_{k-1}$ and this is not lost by replacing edge-replacements adjacent to $v$ with $k$-splits.  So $T_{cs}(G)\geq T_{cs}(\widehat{C})+1\geq3$.  Then it follows that $1\leq T_{cs}(G)-2<\frac{|V(G)|-1}{2a}\leq\frac{7(k-1)}{2a}$, which is a contradiction.

Suppose now that $T_{cs}(G'')=2$.  Then by the minimality of $G$, $|V(G'')|\leq a$.  Because $T_{cs}(G)\geq T_{cs}(G'')+1=3$ it follows that \[1\leq T_{cs}(G)-2<\frac{|V(G)|-1}{2a}\leq\frac{|V(G'')|+6(k-1)-1}{2a}\leq\frac{a+6(k-1)-1}{2a}.\]
From this it follows that $a<6k-7$, which is a contradiction.

Finally, we suppose that $T_{cs}(G'')\geq3$.  Then $\frac{|V(G)|-1}{2a}>T_{cs}(G)-2\geq T_{cs}(G'')-1\geq\frac{|V(G'')|-1}{2a}+1$, so it follows that $|V(G)|>|V(G'')|+2a$.  But $|V(G'')|+6(k-1)\geq|V(G)|$ and these two inequalities show that $6(k-1)>2a$, which is a contradiction.

Therefore we have shown that no two $k$-splits are incident in $\theta^*(\theta^*(G))$.
\end{proof}

We now consider $\theta'(\theta^*(\theta^*(G)))$ which is obtained by taking all $k$-splits in $\theta^*(\theta^*(G))$ and simultaneously edge-reducing them.  By Claim \ref{clm:fatvtxsplit} no edge-replacement is incident to a fat vertex and by Claim \ref{clm:ksplitsdisjoint} no edge-replacement shares an endpoint with another edge-replacement.
%!!!ending 3/17
\begin{claim}
$\theta'(\theta^*(\theta^*(G)))$ is not $K_k$.
\end{claim}
\begin{proof}
To reduce notation, let $G':=\theta^*(\theta^*(G))$ and $G'':=\theta'(\theta^*(\theta^*(G)))$ for this proof. Suppose, for the sake of contradiction, that $G''=K_k$. 
By Claim \ref{**GnotKk}, $\theta^*(\theta^*(G))\neq K_k$ so there must be at least one edge-replacement in $G''$.  Let $m$ be the number of edge-replacements in $G''$ and let $\ell$ be the number of fat vertices in $G''$.  Note that $m\geq1$; also, $2m+\ell\leq k$ because each edge-replacement is adjacent to two distinct vertices which are not fat vertices.

It follows that $T_{cs}(G')\geq m$ as each edge-replacement in $G''$ is a $k$-split in $G'$ with a $K_{k-1}$ subgraph, and $T_{cs}(G)\geq m+\ell$ as each fat vertex in $G''$ corresponds to a diamond or super-diamond in $G$.  Additionally, we know that $|V(G'')|=k$, and $|V(G')|=k+m(k-1)$.  As each $k$-split may have a fat vertex not counted by $\ell$, and all fat vertices in $G'$ could be collapsed super-diamonds, it follows that $|V(G)|\leq  k+m(k-1)+m(2k-2)+\ell(2k-2)=(3m+2\ell+1)(k-1)+1$.

First, suppose that $m\geq3$.  Then $T_{cs}(G)\geq m+\ell\geq3$ and because $G$ is a counterexample it follows that
\[m+\ell-2\leq T_{cs}(G)-2<\frac{|V(G)|-1}{2a}\leq\frac{(3m+2\ell+1)(k-1)}{2a}.\]
So then $2a<\frac{3m+2\ell+1}{m+\ell-2}(k-1)$.  The derivative of $\frac{3m+2\ell+1}{m+\ell-2}$ with respect to $\ell$ is $\frac{-(m+5)}{(m+\ell-2)^2}$ so is negative for all $m\geq3$.  Thus this function is maximized when $\ell=0$ and we have $2a<\frac{3m+1}{m-2}(k-1)$.  Because $m\geq3$ this implies that $2a<10(k-1)$, which is a contradiction.

Second, suppose that $m=2$.  For $\ell\geq1$ we get $T_{cs}(G)\geq m+\ell\geq3$. So it follows that 
\[\ell=m+\ell-2\leq T_{cs}(G)-2<\frac{|V(G)|-1}{2a}\leq\frac{(3m+2\ell+1)(k-1)}{2a}\]
\[=\frac{(2\ell+7)(k-1)}{2a}.\]
This gives $2a<\frac{2\ell+7}{\ell}(k-1)$ and for $\ell\geq1$ implies that $2a<9(k-1)$, which is a contradiction.

Therefore we may assume that $\ell=0$ when $m=2$.  But in this case $T_{cs}(G)\geq3$ as well because each edge-replacement $e,f$ in $G''$ contributes to a $K_{k-1}$ in $G'$ and $G''-\{e,f\}$ is a $K_k-2K_2$, which is a $k$-critical structure that remains intact in $G'$ and $G$.  So then $1\leq T_{cs}(G)-2<\frac{|V(G)|-1}{2a}\leq\frac{7(k-1)}{2a}$, which is a contradiction because $2a\geq7(k-1)$.

Finally, suppose that $m=1$. For $\ell\geq2$ we get $T_{cs}(G)\geq m+\ell\geq3$ so 
\[\ell-1\leq m+\ell-2\leq T_{cs}(G)-2<\frac{|V(G)|-1}{2a}\leq\frac{(2\ell+4)(k-1)}{2a}.\]
This implies that $2a<\frac{2\ell+4}{\ell-1}(k-1)$ and for $\ell\geq2$ it follows that $2a<8(k-1)$, which is a contradiction.

So we may assume that $\ell\leq1$ when $m=1$.  Then $|V(G)|\leq(3m+2\ell+1)(k-1)+1\leq6k-5$.  If $T_{cs}(G)=2$, then we have $a<|V(G)|\leq6k-5$ which is a contradiction.  If $T_{cs}(G)\geq3$ then we have $1\leq T_{cs}(G)-2<\frac{|V(G)|-1}{2a}\leq\frac{6(k-1)}{2a}$.  This implies that $2a<6(k-1)$ which is also a contradiction.

We have shown that all values of $m$ lead to contradiction, so therefore $G''=$
$\theta'(\theta^*(\theta^*(G)))\neq K_k$.
\end{proof}

\begin{claim}
$\theta'(\theta^*(\theta^*(G)))$ contains no diamonds or $k$-splits.
\end{claim}
\begin{proof}
Suppose that $\theta'(\theta^*(\theta^*(G)))$ has a diamond $D$.  It follows from Claim \ref{clm:**GnoDiamond} that $\theta^*(\theta^*(G))$ has no diamonds so it follows that $D$ must have at least one edge-replacement.  Let $\overline{D}$ be the structure in $\theta^*(\theta^*(G))$ obtained from $G$ by replacing each edge-replacement of $D$ with a $k$-split.  Then we can replace each fat vertex in $\overline{D}$ with either a super-diamond or diamond to recover $\widehat{D}\subseteq G$.  Let $G'$ be the graph obtained from $G'$ by collapsing $\widehat{D}$ to $\overline{D}$ and let $G''$ be the graph obtained from $G''$ by edge-reducing any $k$-splits in $\overline{D}$.  Thus $D\subseteq G''$.  Further, let $G'''$ be the graph obtained by collapsing $D$ to a fat vertex $\underline{x}$.  Each of these graphs are $k$-Ore by repeated applications of Proposition \ref{prp:G'Ore}.

Let $m$ be the number of edge-replacements in $D$ and let $\ell$ be the number of fat vertices in $D$.  Note that $m\geq1$.  Then $T_{cs}(\overline{D})\geq m$ and $T_{cs}(\widehat{D})\geq m+\ell$. We claim that $T_{cs}(\widehat{D})\geq2$. If $m\geq2$ this is clear, and if $m=1$, then let $e$ be the edge-replacement in $D$.  $D-e$ is either a $K_k-2K_2$ if $e$ is incident to neither endpoint of $D$, or contains a $K_{k-1}$ if $e$ is incident to an endpoint of $D$.  Thus $T_{cs}(\widehat{D})\geq T_{cs}(\overline{D})=2$.

When replacing $\underline{x}$ with $\widehat{D}$ we possibly lose one $k$-critical structure in $G'''$ but gain at least $\max\{2,m+\ell\}$ from $\widehat{D}$. We claim now that $T_{cs}(G)\geq3$.
For $T_{cs}(G''')\geq2$ there are two cases depending on $m+\ell$.
When $(m+\ell)\geq2$ then $T_{cs}(G)\geq T_{cs}(G''')-1+T_{cs}(\widehat{D})\geq 1+m+\ell$ and when $(m+\ell)=1$ then $T_{cs}(G)\geq T_{cs}(G''')-1+2\geq3$.
The remaining case is when $T_{cs}(G''')=1$ and thus $G'''=K_k$ by Proposition \ref{prp:TKk1}.
Here, $G'''-\{\underline{x}\}$ is a $K_{k-1}$ that remains intact in $G$.  So in fact, no $k$-critical structures from $G'''$ are lost when expanding to $\widehat{D}$ and it follows that $T_{cs}(G)\geq 1+m+\ell$ when $(m+\ell)\geq2$ and $T_{cs}(G)\geq1+T_{cs}(\widehat{D})\geq3$ when $(m+\ell)=1$.
We have shown that $T_{cs}(G)\geq3$ in all cases and, in particular we have
\[T_{cs}(G)\geq \max\{1,T_{cs}(G''')-1\}+2\text{ when }m+\ell=1\text{ and}\]
\begin{equation}\label{eq:lastCase}
T_{cs}(G)\geq \max\{1,T_{cs}(G''')-1\}+m+\ell\text{ when }m+\ell\geq2.
\end{equation}

We also want a bound on $|V(G)|$.  By construction, $|V(G'')|=|V(G''')|+(k-1)$ and $|V(G')|=|V(G''')|+(m+1)(k-1)$. Because each $k$-split in $G'$ may have contained a fat vertex not counted by $\ell$, it follows that 
\[|V(G)|\leq|V(G''')|+(m+1)(k-1)+2(m+\ell)(k-1)\]
\begin{equation}\label{eq:vertexLastCase}
=|V(G''')|+(3m+2\ell+1)(k-1).
\end{equation}

First, suppose that $T_{cs}(G''')\leq2$ so that $|V(G''')|\leq a$.
When $m+\ell\geq2$ it follows that
\[m+\ell-1\leq T_{cs}(G)-2<\frac{|V(G)|-1}{2a}\leq\frac{a+(3m+2\ell+1)(k-1)-1}{2a}\]
\[<\frac{1}{2}+\frac{3(m+\ell)+1}{2a}(k-1).\]
This implies that $a<\frac{3(m+\ell)+1}{2(m+\ell)-3}(k-1)$ and for $(m+\ell)\geq2$ we get $a<7(k-1),$ which is a contradiction.
When $(m+\ell)=1$ then it must be that $m=1$ and $\ell=0$.  But now because $1\leq T_{cs}(G)-2<\frac{|V(G)|-1}{2a}\leq\frac{a+4(k-1)-1}{2a}$, it follows that $a<4k-5$, which is also a contradiction.

Now suppose that $T_{cs}(G''')\geq3$.  
When $m+\ell\geq2$ then we have, because $G'''$ follows Theorem \ref{thm:Main2}, $\frac{|V(G)|-1}{2a}>T_{cs}(G)-2\geq(T_{cs}(G''')-1+m+\ell)-2\geq\frac{|V(G''')|-1}{2a}-1+m+\ell$.  This implies that $|V(G)|>|V(G''')|+2a(m+\ell-1)$.  But we also have that $|V(G)|\leq|V(G''')|+(3m+2\ell+1)(k-1)\leq|V(G''')|+(3(m+\ell)+1)(k-1)$.
Together, these inequalities show that $2a<\frac{3(m+\ell)+1}{(m+\ell)-1}(k-1)$.
For $(m+\ell)\geq2$ it follows that $2a<7(k-1)$, which is a contradiction.  

When $m+\ell=1$ then $\ell=0$ and we have
\[\frac{|V(G)|-1}{2a}>T_{cs}(G)-2\geq(T_{cs}(G''')-1+2)-2\geq\frac{|V(G''')|-1}{2a}+1.\]
This implies that $|V(G)|>|V(G''')|+2a$ but we also have that $|V(G''')|+4(k-1)\geq|V(G)|$.
Together these inequalities show that $4(k-1)>2a$, which is a contradiction.
Therefore there can be no diamonds $D$ in $\theta'(\theta^*(\theta^*(G)))$.

Now suppose that $\theta'(\theta^*(\theta^*(G)))$ contains a $k$-split $C$.  Because all $k$-splits in $\theta^*(\theta^*(G))$ are now edge-replacements in $\theta'(\theta^*(\theta^*(G)))$, at least one edge of $C$ must be an edge-replacement.  Let $\overline{C}$ be the subgraph of $\theta^*(\theta^*(G))$ obtained from $C$ by replacing each edge-replacement of $C$ with a $k$-split.  Then we can replace each fat vertex in $\overline{C}$ with either a super-diamond or diamond to recover $\widehat{C}\subseteq G$.  Let $G'$ be the graph obtained from $G$ by collapsing $\widehat{C}$ to $\overline{C}$ and let $G''$ be the graph obtained from $G'$ by edge-reducing any $k$-splits in $\overline{C}$.  Thus $C\subseteq G''$.  Further, let $G'''$ be the graph obtained from $G''$ by edge-reducing $C$ to the edge-replacement $f=uv$. Each of these graphs are $k$-Ore by repeated applications of Proposition \ref{prp:G'Ore}.

Let $m$ be the number of edge-replacements in $C$ and let $\ell$ be the number of fat vertices in $C$.  Note that $m\geq1$.  
Also $T_{cs}(\overline{C})\geq m$ and $T_{cs}(\widehat{C})\geq m+\ell$. 
We claim that $T_{cs}(\widehat{C})\geq2$. If $m\geq2$ this is clear, and if $m=1$, then let $e$ be the edge-replacement in $C$.  $C-e$ is either in $\mathbb{H}$ if $e$ is incident to neither endpoint of $C$, or contains a $K_{k-1}$ if $e$ is incident to an endpoint of $C$.  Thus $T_{cs}(\widehat{C})\geq T_{cs}(\overline{C})=2$.

When replacing $f=uv$ with $\widehat{C}$ we possibly lose one $k$-critical structure in $G'''$ 
%%%%%12/9 this is not strictly true
but gain at least $\max\{2,m+\ell\}$ from $\widehat{C}$.  
Exactly as in the diamond case above, if $T_{cs}(G''')\geq2$ then $T_{cs}(G)\geq T_{cs}(G''')-1+T_{cs}(\widehat{C})$.
Also, if $T_{cs}(G''')=1$ then $G'''=K_k$ by Proposition \ref{prp:TKk1} and $G'''-f$ contains a $K_{k-1}$ that remains intact in $G$.  
%%%%Again, this is not necessarily true, I think
So in fact, no $k$-critical structures from $G'''$ were lost and it follows that $T_{cs}(G)\geq 1+m+\ell$ when $(m+\ell)\geq2$ and $T_{cs}(G)\geq1+T_{cs}(\widehat{C})\geq3$ when $(m+\ell)=1$.

Therefore when $G'''$ has a $k$-split, Equations \ref{eq:lastCase} and \ref{eq:vertexLastCase} also hold, just as they did when $G'''$ had a diamond. 
Thus, the same arguments will also lead to contradictions for $k$-splits $C\subseteq\theta'(\theta^*(\theta^*(G)))$.  Therefore, we have shown that $\theta'(\theta^*(\theta^*(G)))$ contains no diamonds or $k$-splits.
\end{proof}

\textit{End of proof of Theorem \ref{thm:Main2}.}
Now we have a graph $H=\theta'(\theta^*(\theta^*(G)))$ which is not $K_k$, and contains no diamonds or $k$-splits.  By repeated applications of Proposition \ref{prp:G'Ore} we know that $H$ is $k$-Ore.  Because $H$ is not $K_k$ it follows that $H$ is an Ore composition of two $k$-Ore graphs $H_1$ and $H_2$ with overlap vertices $\{u,v\}$.  Because $H$ contains no diamonds or $k$-splits, $T_{cs}(H_i)\geq2$ for $i=1,2$.

We replace all edge-replacements in $E(H)$ and all fat vertices in $V(H)-\{u,v\}$ with the structures that were originally subgraphs of $G$.  This gives a graph $G'$ where $G'=G$ if neither $u$ nor $v$ is a fat vertex in $H$, or where we could obtain $G'$ from $G$ by collapsing the necessary diamonds or super-diamonds into the fat vertices $u$ or $v$. Thus it follows that $T_{cs}(G)\geq T_{cs}(G')$. Also $G'$ is $k$-Ore and we can realize $G'$ as an Ore composition of two $k$-Ore graphs $G'_1$ and $G'_2$ with overlap vertices $\{u,v\}$ (the same as the overlap vertices of $H$).
Because $T_{cs}(G'_i)\geq T_{cs}(H_i)$ for $i=1,2$, we know that $T_{cs}(G'_i)\geq2$ for $i=1,2$.  We break the proof of the theorem into three cases.  %6/20/14

First, we consider the case where $T_{cs}(G'_1)=T_{cs}(G'_2)=2$.  If $T_{cs}(G'_1)=2$ then it follows that $T_{cs}(H_1)=2$.  But $H_1-uv$ has no diamonds, so Lemma \ref{lem:TG2} implies that $T_{cs}(H_1-uv)=2$.  Thus, $T_{cs}(G'_1-uv)=2$ as well.  A similar argument shows that $T_{cs}(G'_2-\{\underline{uv}\})=2$.  But this gives 4 disjoint critical structures in $G'$ so we know that $4\leq T_{cs}(G')\leq T_{cs}(G)$.  Also, by the minimality of $G$, we have that $|V(G'_i)|\leq a$ for $i=1,2$.  Thus $|V(G')|\leq2a-1$ and because the vertices $u,v$ could be at worst super-diamonds, it follows that $|V(G)|\leq2a-1+4(k-1)$.  Putting these inequalities together we have that
\[2\leq T_{cs}(G)-2<\frac{|V(G)|-1}{2a}\leq1+\frac{4k-5}{2a}.\]
This implies that $2a<4k-5$, which is a contradiction.%6/20/14

Second, we consider the case where one of $T_{cs}(G'_1)$ and $T_{cs}(G'_2)$ is 2, and the other is at least 3.  Suppose that $T_{cs}(G'_1)=2$.  Then, by Lemma \ref{lem:TG2}, it follows that $T_{cs}(G'_1-e)=2$.
Thus $T_{cs}(G)\geq T_{cs}(G')\geq 2+T_{cs}(G'_2)-1=T_{cs}(G'_2)+1$ by Lemma \ref{lem:gluing}.  Also, we have that $|V(G'_1)|\leq a$ which implies that $|V(G)|\leq |V(G'_2)|+a+4k-5$.  However we then have the string of inequalities
\[T_{cs}(G'_2)-1\leq T_{cs}(G)-2<\frac{|V(G)|-1}{2a}\leq\frac{|V(G'_2)|-1}{2a}+\frac{a+4k-5}{2a}.\]
Because Theorem \ref{thm:Main2} holds for $G'_2$, this implies that $1<\frac{a+4k-5}{2a}$, or that $a<4k-5$ which is a contradiction.  A similar argument yields a contradiction when $T_{cs}(G'_2)=2$ and $T_{cs}(G'_1)\geq3$.%6/20/14

Third, we consider the case where $T_{cs}(G'_1)$ and $T_{cs}(G'_2)$ are both at least 3.  If $u,v\in V(G')$ are not fat vertices, then $G'=G$ and we have that $|V(G)|=|V(G'_1)|+|V(G'_2)|-1$.  Then it follows from Lemma \ref{lem:gluing} that 
\[T_{cs}(G)-2\geq T_{cs}(G'_1)+T_{cs}(G'_2)-4\geq \frac{|V(G'_1)|-1}{2a}+\frac{|V(G'_2)|-1}{2a}=\frac{|V(G)|-1}{2a}.\]
This contradicts the fact that $G$ is a counterexample.%6/20/14

Therefore we may assume that at least one of $u$ or $v$ is a fat vertex in $G'$.  We claim that $T_{cs}(G)\geq T_{cs}(G'_1)+T_{cs}(G'_2)-1$; if this can be shown, then it follows that 
\[T_{cs}(G)-2\geq T_{cs}(G'_1)+T_{cs}(G'_2)-4+1\]
\[\geq \frac{|V(G'_1)|-1}{2a}+\frac{|V(G'_2)|-1}{2a}+\frac{2a}{2a}\geq\frac{|V(G)|-1}{2a}\]
where the last inequality is because $|V(G)|\leq|V(G'_1)|+|V(G'_2)|-1+4(k-1)\leq|V(G'_1)|+|V(G'_2)|-1+2a$.  This would contradict the fact that $G$ is a counterexample.

To show the claim we will first assume that exactly one of $u,v$ is a fat vertex in $G'$ and, without loss of generality, suppose that it is $u$.
The graphs $G'_2-\{\underline{uv}\}$ and $G'_1-\{u\}$ are disjoint subgraphs in $G$, so it follows using an argument similar to the proof of Lemma \ref{lem:gluing} that $T_{cs}(G)\geq T_{cs}(G'_1)-1+T_{cs}(G'_2)-1$.
No $k$-critical structure in this lower bound uses the vertex $u\in V(G')$ and so when we expand that fat vertex, we gain an additional $k$-critical structure.
Therefore $T_{cs}(G)\geq T_{cs}(G'_1)+T_{cs}(G'_2)-1$.

Now assume that both $u$ and $v$ are fat vertices in $G'$.
The graphs $G'_2-\{\underline{uv}\}$ and $G'_1-\{u,v\}$ are disjoint subgraphs in $G$, so it follows using an argument similar to the proof of Lemma \ref{lem:gluing} that $T_{cs}(G)\geq T_{cs}(G'_1)-2+T_{cs}(G'_2)-1$.
No $k$-critical structure in this lower bound use the vertices $u,v\in V(G')$ and so when we expand the two fat vertices, we gain two additional $k$-critical structures.
Therefore $T_{cs}(G)\geq T_{cs}(G'_1)+T_{cs}(G'_2)-1$.

We have shown that $T_{cs}(G)\geq T_{cs}(G'_1)+T_{cs}(G'_2)-1$ whenever at least one of $u$ or $v$ is a fat vertex in $G'$, and thus the case where $T_{cs}(G'_1)$ and $T_{cs}(G'_2)$ are both at least 3 will also lead to a contradiction.  This completes the proof of Theorem \ref{thm:Main2}.
\end{proof}


%commentedout (12/11) to make DTF application prettier
%Here we cite \cite{mybibitem} to make the bibliography work.

