% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures % use this command to create hyperlinks (optional and recommended) % use these commands for typesetting doi and arXiv references in the bibliography % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins \def\COMMENT#1{} %\let\COMMENT=\footnote \def\C{\mathcal{C}} \def\eps{\varepsilon} \def\ex{\mathbb{E}} \def\prob{\mathbb{P}} \def\eul{{\rm e}} % declare theorem-like environments \theoremstyle{plain} \newtheorem{firstthm}{Proposition} \newtheorem{thm}[firstthm]{Theorem} \newtheorem{prop}[firstthm]{Proposition} \newtheorem{fact}[firstthm]{Fact} \newtheorem{lemma}[firstthm]{Lemma} \newtheorem{cor}[firstthm]{Corollary} \newtheorem{problem}[firstthm]{Problem} \newtheorem{defin}[firstthm]{Definition} \newtheorem{conj}[firstthm]{Conjecture} \newtheorem{claim}[firstthm]{Claim} \newtheorem{ques}[firstthm]{Question} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{On perfect packings in dense graphs} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{J\'ozsef Balogh,\footnote{University of Illinois, Urbana-Champaign, USA and University of California, San Diego, USA, jobal@math.uiuc.edu. This author is supported by NSF CAREER Grant DMS-0745185, UIUC Campus Research Board Grant 11067, and OTKA Grant K76099.} \ Alexandr V. Kostochka\footnote{ University of Illinois, Urbana-Champaign, USA and Institute of Mathematics, Novosibirsk, Russia, kostochk@math.uiuc.edu. This author is supported in part by NSF grant DMS-0965587 and by grant 12-01-00631 of the Russian Foundation for Basic Research.} \ and Andrew Treglown\footnote{Queen Mary, University of London, United Kingdom, treglown@maths.qmul.ac.uk}} % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{June 30, 2011}{Feb 8, 2013}\\ \small Mathematics Subject Classifications: 05C15, 05C35, 05C70} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract will be distributed without the rest of the % paper so it must be entirely self-contained. \begin{abstract} We say that a graph $G$ has a perfect $H$-packing if there exists a set of vertex-disjoint copies of $H$ which cover all the vertices in $G$. We consider various problems concerning perfect $H$-packings: Given $n, r , D \in \mathbb N$, we characterise the edge density threshold that ensures a perfect $K_r$-packing in any graph $G$ on $n$ vertices and with minimum degree $\delta (G) \geq D$. We also give two conjectures concerning degree sequence conditions which force a graph to contain a perfect $H$-packing. Other related embedding problems are also considered. Indeed, we give a structural result concerning $K_r$-free graphs that satisfy a certain degree sequence condition. \end{abstract} \section{Introduction} Given two graphs $H$ and $G$, a \emph{perfect $H$-packing} in $G$ is a collection of vertex-disjoint copies of $H$ which cover all the vertices in $G$. Perfect $H$-packings are also referred to as \emph{$H$-factors} or \emph{perfect $H$-tilings}. Hell and Kirkpatrick~\cite{hell} showed that the decision problem whether a graph $G$ has a perfect $H$-packing is NP-complete precisely when $H$ has a component consisting of at least $3$ vertices. So for such graphs $H$, it is unlikely that there is a complete characterisation of those graphs containing a perfect $H$-packing. Thus, there has been significant attention on obtaining sufficient conditions that ensure a graph $G$ contains a perfect $H$-packing. A seminal result in the area is the Hajnal-Szemer\'edi theorem~\cite{hs} which states that a graph $G$ whose order $n$ is divisible by $r$ has a perfect $K_r$-packing provided that $\delta (G) \geq (r-1)n/r$. K\"uhn and Osthus~\cite{kuhn, kuhn2} characterised, up to an additive constant, the minimum degree which ensures a graph $G$ contains a perfect $H$-packing for an arbitrary graph $H$. It is easy to see that the minimum degree condition in the Hajnal-Szemer\'edi theorem cannot be lowered. Of course, this does not mean that one cannot strengthen this result. \emph{Ore-type} degree conditions consider the sum of the degrees of non-adjacent vertices in a graph. The following Ore-type result of Kierstead and Kostochka~\cite{kier} implies the Hajnal-Szemer\'edi theorem. \begin{thm}[Kierstead and Kostochka~\cite{kier}]\label{orekk} Let $n,r \in \mathbb N$ such that $r $ divides $n$. Suppose that $G$ is a graph on $n$ vertices such that for all non-adjacent $x \not =y \in V(G)$, $$d(x)+d(y) \geq 2(1-1/r)n-1 .$$ Then $G$ contains a perfect $K_r$-packing. \end{thm} K\"uhn, Osthus and Treglown~\cite{kotore} characterised, asymptotically, the Ore-type degree condition which ensures a graph $G$ contains a perfect $H$-packing for an arbitrary graph $H$. \subsection{Perfect packings in dense graphs of low minimum degree} It is easy to characterise the edge density that forces a graph $G$ to contain a perfect $K_r$-packing when there are no other restrictions. Indeed, given $n,r \in \mathbb N$ such that $r \geq 2$ divides $n$, if $G$ is a graph on $n$ vertices and $e(G) \geq \binom{n}{2}- n+r$ then $G$ contains a perfect $K_r$-packing. Moreover, if $G$ is a copy $K$ of $K_{n-1}$ together with a vertex which sends precisely $r-2$ edges to $K$, then $e(G)=\binom{n}{2}- n+r-1$ and $G$ does not contain a perfect $K_r$-packing. The following result of Akiyama and Frankl~\cite{frank} refines this observation. \begin{thm}[Akiyama and Frankl~\cite{frank}]\label{frank} Let $n,r \in \mathbb N$ such that $r$ divides $n$. Suppose $G$ is a graph on $n$ vertices and $e(\overline{G}) \leq \min \{ \binom{n/r+1}{2} , n-r+1 \}$. Then $G$ has a perfect $K_r$-packing unless $\overline{G}$ is isomorphic to one of the following graphs: \begin{itemize} \item[(i)] A copy of $K_{n/r+1}$ together with $(1-1/r)n-1$ isolated vertices; \item[(ii)] The disjoint union of $K_{1,n-r-j+1}$, $j$ edges and $r-j-2$ isolated vertices, for some $1\leq j \leq r-2$. \end{itemize} \end{thm} When (for example) $n \geq r^3$, $\binom{n/r+1}{2} > n-r+1$. Hence, in this case Theorem~\ref{frank} is equivalent to the following: If $G$ is a graph on $n$ vertices and $e(G)\geq \binom{n}{2}- n+r-1$ then either $G$ contains a perfect $K_r$-packing or $\overline{G}$ is isomorphic to a graph as in (ii). In Sections~\ref{edgeexsec} and~\ref{edgesec} we consider the following natural problem: Let $n,r \in \mathbb N$ such that $r$ divides $n$. Given some $D \in \mathbb N$, what edge density condition ensures that any graph $G$ on $n$ vertices and of minimum degree $\delta (G) \geq D$ contains a perfect $K_r$-packing? We fully resolve the problem, and our answers for $r=2$ and $r\geq 3$ differ. \begin{thm}\label{p1} For an even positive $n$ and integer $1\leq dg(n,r,D)$. Then $G$ contains a perfect $K_r$-packing. Moreover, there exists a graph $G'$ on $n$ vertices with $\delta (G')\geq D$ and $e(G')=g(n,r,D)$ but such that $G'$ does not contain a perfect $K_r$-packing. \end{thm} Clearly a graph $G$ of minimum degree $\delta (G) 0$ and $H$ is a graph with $\chi (H)=r$. Then there exists an integer $n_0=n_0 (\gamma ,H)$ such that the following holds. If $G$ is a graph whose order $n \geq n_0$ is divisible by $|H|$, and whose degree sequence $d_1\leq \dots \leq d_n$ satisfies \begin{itemize} \item $d_i \geq (r-2)n/r+i +\gamma n $ for all $i < n/r$, \end{itemize} then $G$ contains a perfect $H$-packing. \end{conj} Since first submitting this paper, the third author and~Knox~\cite{knox} have proven Conjecture~\ref{conj2} in the case when $r=2$. (In fact, they have proven a much more general result concerning embedding spanning bipartite graphs of small bandwidth.) The following result of Erd\H{o}s~\cite{erdos1} characterises those degree sequences which force a copy of $K_r$ in a graph $G$. \begin{thm}[Erd\H{o}s~\cite{erdos1}] Let $G$ be a graph on $n$ vertices with degree sequence $d_1\leq \dots \leq d_n$. If $G$ is $K_{r+1}$-free then there is an $r$-partite graph $G'$ on $n$ vertices whose degree sequence $d'_1\leq \dots \leq d'_n$ satisfies $$d_i \leq d'_i \ \text{ for all } \ i \leq n.$$ \end{thm} In Section~\ref{turansec} we prove the following related structural theorem. \begin{thm}\label{turan} Suppose that $n,r \in \mathbb N$ such that $n \geq r$ and so that $r$ divides $n$. Let $G$ be a $K_{r+1}$-free graph on $n$ vertices whose degree sequence $d_1 \leq \dots \leq d_n$ is such that $d_{ n/r } \geq (r-1)n/r$. Then $G \subseteq T(n,r)$, where $T(n,r)$ is the complete $r$-partite \emph{Tur\'an graph} on $n$ vertices; so each vertex class has size $\lceil n/r \rceil$ or $\lfloor n/r \rfloor$. \end{thm} %%%%%%%%%%%%%%%%%% \section{The case $r=2$ and extremal examples for $r\geq 3$}\label{edgeexsec} \subsection{Perfect matchings in dense graphs}\label{sectutte} In this section we establish the density threshold that ensures every graph $G$ on an even number $n$ of vertices and of minimum degree $\delta (G) \geq d$ contains a perfect matching. Note that we only consider values of $d$ such that $1 \leq d \max\{h(n,d),$ $h(n,0.5n-1)\}$ has a perfect matching. Consider such a graph $G$. Let $d_1 \leq \dots \leq d_n$ denote the degree sequence of $G$. If $d_i \geq i$ for all $1 \leq i \leq n/2$ then Theorem~\ref{hampath} implies that $G$ contains a perfect matching. Suppose for a contradiction that $d_{i'} \leq i'-1$ for some $1 \leq i' \leq n/2$. Note that $i' >d$ as $\delta (G) \geq d$. Let $A$ denote the set of $i'$ vertices in $G$ that correspond to the first $i'$ terms $d_1 , \dots , d_{i'}$ of the degree sequence. Set $B:=V(G) \backslash A$. Then $$e(G[B]) \geq e(G) - i'(i'-1) > \max\{h(n,d),h(n,0.5n-1)\} - i'(i'-1)$$ since $d(x) \leq i'-1$ for all $x \in A$. Note that $\max\{h(n,d),h(n,0.5n-1)\} \geq h(n,i'-1)$ since $d\max\{h(n,d),h(n,0.5n-1)\} - i'(i'-1) \geq h(n,i'-1) -i'(i'-1){=} \binom{n-i'}{2},$$ a contradiction as $|B|=n-i'$. Thus, $d_i \geq i$ for all $1 \leq i \leq n/2$, as desired. %\endproof \subsection{Examples for $r\geq 3$} We will give the extremal examples for Theorem~\ref{t1}. Since Theorems~\ref{mainthm1} and~\ref{t1} are equivalent, the complements of the extremal graphs for Theorem~\ref{t1} are the extremal graphs for Theorem~\ref{mainthm1}. \begin{prop}\label{propex1} Suppose that $n,r \in \mathbb N$ such that $r\geq 3$ and $r$ divides $n$. Then there exists a graph $G_1$ on $n$ vertices such that $\Delta (G_1)=n/r$, $$e(G_1)=\binom{n/r+1}{2},$$ but such that $G_1$ does not have an equitable $n/r$-colouring. \end{prop} \proof Let $G_1$ denote the disjoint union of a clique $V$ on $n/r+1$ vertices and an independent set $W$ of $(1-1/r)n-1$ vertices. So every independent set in $G_1$ contains at most one vertex from $V$. But since $|V|=n/r+1$, $G_1$ does not have an equitable $n/r$-colouring. Further, $\Delta (G_1)=n/r$ and $e(G_1)=\binom{n/r+1}{2}.$ \endproof \begin{prop}\label{propex2} Suppose that $n,r \in \mathbb N$ such that $r\geq 3$ and $n=kr$ for some $k \geq 2$. Further, let $D \in \mathbb N$ such that $n/(r-1) \leq D \leq n-r$. Then there exists a graph $G_2$ on $n$ vertices such that $\Delta (G_2)=D$, $$e(G_2)=D+e(\overline{T}(n-D-1, r-2)) ,$$ but such that $G_2$ does not have an equitable $n/r$-colouring. \end{prop} \proof Let $G_2$ denote the disjoint union of a copy $K$ of $K_{1,D}$ and a copy of $\overline{T}(n-D-1, r-2)$. So $|G|=n$. Let $v$ denote the vertex of degree $D$ in $K$. The largest independent set in $G_2$ that contains $v$ is of size $r-1$. Thus, $G_2$ does not have an equitable $n/r$-colouring. Further, $e(G_2)=D+e(\overline{T}(n-D-1, r-2)).$ Since $n/(r-1)\leq D$ we have that $n-1 \leq (r-1)D$. Thus, every vertex in the copy of $\overline{T}(n-D-1, r-2)$ has degree at most $$\left \lceil \frac{n-D-1}{r-2} \right \rceil -1 \leq \frac{n-D-1}{r-2} \leq D.$$ This implies that $\Delta (G_2)=D$. \endproof \COMMENT{Awkward that the example in Prop~\ref{propex2} does not have $\Delta (G_2)=D$ if $D 0 \end{align*} for all $r \in \mathbb N$ such that $r \geq 3$. \subsection{Case 3: $\bf D'=D$ and $ \bf f(n',r, D')=D'+ e(\overline{T}(n'-D'-1,r-2))$.} By (\ref{contra1}) we have that \begin{align}\label{thresh1} e(G') \geq f(n',r,D')=D'+ e(\overline{T}(n'-D'-1,r-2)). \end{align} Consider any vertex $x \in V(G')$ such that $d_{G'} (x)=D'=D$. Since $\Delta (G)=D$, $x$ is not adjacent to any vertex in $I=\{v, x_1, \dots , x_{r-1} \}$. Further, $I$ was chosen such that $d_G (x_1)+\dots +d_G (x_{r-1})$ is maximised. Thus, $d_G(x_1)=\dots =d_G (x_{r-1})=D$. Together with (\ref{thresh1}) this implies that \begin{align}\label{thresh2} e(G)\geq (r+1)D +e(\overline{T}(n'-D-1,r-2)). \end{align} Since $e(G)|V_{r}|$ this implies that $G$ does not contain a perfect $K_r$-packing. Furthermore, $G$ has our desired degree sequence. \endproof \COMMENT{Add picture!} Notice that the graphs $G$ considered in Proposition~\ref{extremal1} satisfy ($\beta$) from Conjecture~\ref{conj1} and only fail to satisfy ($\alpha$) in the case when $i=k$ (and in this case $d_k =(r-2)n/r+k-1$). \medskip Let $n,r \in \mathbb N$ such that $r$ divides $n$. Denote by $T^*(n,r)$ the complete $r$-partite graph on $n$ vertices with $r-2$ vertex classes of size $n/r$, one vertex class of size $n/r-1$ and one vertex class of size $n/r+1$. Then $T^*(n,r)$ does not contain a perfect $K_r$-packing. Furthermore, $T^*(n,r)$ satisfies ($\alpha$) but condition ($\beta$) fails; we have that $d _{n/r+1}=(r-1)n/r-1$ here. Thus, together $T^*(n,r)$ and Proposition~\ref{extremal1} show that, if true, Conjecture~\ref{conj1} is essentially best possible. \section{A special case of Conjecture~\ref{conj1}}\label{sec2} We now give a simple proof of Conjecture~\ref{conj1} in the case when $G$ is $K_{r+1}$-free. %We now prove Conjecture~\ref{conj1} in the case when $r=2$. %\begin{prop} %Suppose that $G$ is a graph on an even number $n$ of vertices with degree sequence $d_1 \leq %\dots \leq d_n$ such that: %\begin{itemize} %\item[(1)] $d_i \geq i $ for all $i < n/2$; %\item[(2)] $d_{n/2+1} \geq n/2$. %\end{itemize} %Then $G$ contains a perfect matching. %\end{prop} %\proof %Suppose for a contradiction that there is a graph $G$ on $n$ vertices whose degree sequence $d_1 \leq \dots \leq d_n$ satisfies %(1)--(2) but which does not contain a perfect matching. By adding edges to $G$ if necessary, we may also assume that $G$ contains %a matching $M$ of size $n/2-1$. Amongst all those matchings in $M$ of size $n/2-1$, %choose $M$ so that $d_G(x)+d_G(y)$ is maximised where $\{x,y\}:=V(G)\backslash M$. %Note that $d_G (x), d_G (y)\geq n/2-1$. Indeed, suppose for a contradiction that $\ell :=d_G (x) d_G (x)+d_G (y)$. This contradicts the choice of $M$, as desired. %We may assume that $d_G (x)\geq d_G (y)$. We may also assume that $d_G (x) \geq n/2$. (Indeed, if this is not the case then % $d_G (x)=d_G (y)=n/2-1$. Further, %$xy \not \in E(G)$. Since $|N^* _G (x)|=n/2-1$, (2) implies that there exists a vertex $x' \in N^* _G (x)$ such that %$d_G (x') \geq d_{n/2+1} \geq n/2$. Suppose $y'$ is adjacent to $x'$ in $M$. Then replacing $x'y'$ with $xy'$ in $M$, we obtain %a matching of size $n/2-1$ which leaves $x'$ and $y$ uncovered where $d_G (x')\geq n/2$ and $d_G (y)= n/2-1$.) Since %$d_G (x) \geq n/2$ and $d_G (y) \geq n/2-1$, %there exists an edge $wz$ in $M$ such that $x$ is adjacent to $w$ and $y$ is adjacent to $z$. But then %$(M\backslash \{wz\})\cup \{xw,yz\}$ is a perfect matching, a contradiction, as desired. %\endproof \begin{thm}\label{Krfree} Let $n,r \in \mathbb N$ such that $r \geq2 $ divides $n$. Suppose that $G$ is a graph on $n$ vertices with degree sequence $d_1 \leq \dots \leq d_n$ such that: \begin{itemize} \item $d_i \geq (r-2)n/r+i $ for all $i < n/r$; \item $d_{n/r+1} \geq (r-1)n/r$. \end{itemize} Further suppose that no vertex $x \in V(G)$ of degree less than $(r-1)n/r$ lies in a copy of $K_{r+1}$. Then $G$ contains a perfect $K_r$-packing. \end{thm} \proof We prove the theorem by induction on $n$. In the case when $n=r$ then $d_{n/r+1}=d_2\geq (r-1)r/r=r-1$. This implies that every vertex in $G$ has degree $r-1$. Hence $G=K_r$ as desired. So suppose that $n>r$ and the result holds for smaller values of $n$. Let $x_1 \in V(G)$ such that $d_G(x_1)=d_1 \geq (r-2)n/r+1$. If $d_G (x_1) \geq (r-1)n/r$ then $\delta (G)\geq (r-1)n/r$. Thus $G$ contains a perfect $K_r$-packing by the Hajnal-Szemer\'edi theorem. So we may assume that $(r-2)n/r+1\leq d_G (x_1) <(r-1)n/r$. In particular, $x_1$ does not lie in a copy of $K_{r+1}$. We first find a copy of $K_r$ containing $x_1$. If $r=2$, $x_1$ has a neighbour and so we have our desired copy of $K_2$. So assume that $r\geq 3$. Certainly $N_G(x_1)$ contains a vertex $x_2$ such that $d_G(x_2) \geq (r-1)n/r$. Thus, $|N_G(x_1)\cap N_G(x_2)|\geq (r-3)n/r+1 >0$. So if $r=3$ we obtain our desired copy of $K_r$. Otherwise, we can find a vertex $x_3 \in N_G(x_1)\cap N_G(x_2)$ such that $d_G(x_3) \geq (r-1)n/r$. We can repeat this argument until we have obtained vertices $x_1, \dots , x_r$ that together form a copy $K'_r$ of $K_r$. Let $G':=G-V(K'_r)$ and set $n':=n-r=|V(G')|$. Since $G$ does not contain a copy of $K_{r+1}$ containing $x_1$, every vertex $x \in V(G)\backslash V(K'_r)$ sends at most $r-1$ edges to $K'_r$ in $G$. Thus, $d_{G'} (x) \geq d_G (x) -(r-1)$ for all $x \in V(G')$. So if $d_G (x) \geq (r-1)n/r$ then $d_{G'} (x) \geq (r-1)n/r -(r-1)=(r-1)n'/r$ for all $x \in V(G')$. If a vertex $y \in V(G')$ does not lie in a copy of $K_{r+1}$ in $G$ then clearly $y$ does not lie in a copy of $K_{r+1}$ in $G'$. This means that no vertex $y \in V(G')$ of degree less than $(r-1)n'/r$ lies in a copy of $K_{r+1}$. Let $d'_1 \leq \dots \leq d'_{n'}$ denote the degree sequence of $G'$. It is easy to check that $d'_i \geq {(r-2)n'}/{r}+i$ for all $i < n'/r$ and that $d'_{n'/r+1} \geq (r-1)n'/r$. Indeed, since $x_1 \in V(K'_r)$ where $d_G (x_1)=d_1$, we have that $d'_i \geq d_{i+1}-(r-1)$ for all $1 \leq i \leq n'$. Thus, for all $1 \leq i < n'/r=n/r-1$, $d'_i \geq d_{i+1}-(r-1) \geq (r-2)n/r+(i+1)-(r-1)=(r-2)n'/r+i$. Similarly, $d'_{n'/r+1}=d'_{n/r} \geq d_{n/r+1}-(r-1)\geq (r-1)n/r-(r-1)=(r-1)n'/r$. Hence, by induction $G'$ contains a perfect $K_r$-packing. Together with $K'_r$ this gives us our desired perfect $K_r$-packing in $G$. \endproof %%%%%%%%%%%%%%%%% \section{Proof of Theorem~\ref{turan}}\label{turansec} Consider any $x_1 \in V(G)$ such that $d_G(x_1)\geq (r-1)n/r$. Since $d_{n/r} \geq (r-1)n/r$ we can greedily select vertices $x_2, \dots , x_{r-1}$ such that \begin{itemize} \item $x_1, \dots , x_{r-1}$ induce a copy of $K_{r-1}$ in $G$; \item $d_G(x_i) \geq (r-1)n/r$ for all $1 \leq i \leq r-1$. \end{itemize} Note that since $G$ is $K_{r+1}$-free, $\cap ^{r-1} _{i=1} N_G (x_i)$ is an independent set. The choice of $x_1, \dots ,$ $x_{r-1}$ implies that $|\cap ^{r-1} _{i=1} N_G (x_i)|\geq n/r$. Let $V_1$ denote a subset of $\cap ^{r-1} _{i=1} N_G (x_i)$ of size $n/r$. Thus $V_1$ contains a vertex $x^1 _1$ of degree at least $(r-1)n/r$. As before we can find vertices $x^1_2, \dots , x^1_{r-1}$ such that \begin{itemize} \item $x^1 _1, \dots , x^1 _{r-1}$ induce a copy of $K_{r-1}$ in $G$; \item $d_G(x^1_i) \geq (r-1)n/r$ for all $1 \leq i \leq r-1$. \end{itemize} So $\cap ^{r-1} _{i=1} N_G (x^1 _i)$ is an independent set of size at least $n/r$. Let $V_2$ denote a subset of $\cap ^{r-1} _{i=1} N_G (x^1 _i)$ of size $n/r$. Note that $N_G (x^1 _1) \cap V_1=\emptyset$ since $x^1 _1 \in V_1$ and $V_1$ is an independent set. Thus as $V_2 \subseteq N_G (x^1 _1)$, $V_1 \cap V_2 =\emptyset$. Our aim is to find disjoint sets $V_1, \dots , V_r \subseteq V(G)$ of size $n/r$ and vertices $x^1 _1, \dots, x^1 _{r-1},$ $x^2 _1, \dots, x^2 _{r-1}$, $\dots , x^{r-1} _1, \dots, x^{r-1} _{r-1}$ with the following properties: \begin{itemize} \item $G[V_j]$ is an independent set for all $1 \leq j \leq r$; \item Given any $1\leq j \leq r-1$, $x^j _k \in V_k$ for each $1 \leq k \leq j$; \item $d_G (x^j _k) \geq (r-1)n/r$ for all $1 \leq j \leq r-1$ and $1 \leq k \leq r-1$; \item $x^j _1, \dots , x^j _{r-1}$ induce a copy of $K_{r-1}$ in $G$ for all $1 \leq j \leq r-1$. \end{itemize} Clearly finding such a partition $V_1, \dots , V_r$ of $V(G)$ implies that $G \subseteq T(n,r)$. Suppose that for some $1< j 3r/2+4$. So $n> 3(r-1)/2+(2r-1)/(r-2)$. Thus, $$h'(x) \leq -\frac{n}{r-1}+\frac{1}{r-2}+\frac{r}{(r-1)(r-2)}+\frac{3}{2} <0,$$ as desired. \endproof \medskip \noindent {\bf Proof of Proposition~\ref{propex3}.} We need to show that, for all $D \in \mathbb N$ such that $n/r \leq D \leq n/(r-1)$, $$\frac{n^2}{2r^2}+\frac{n}{2r} =\binom{n/r+1}{2} \leq D+e(\overline{T}(n-D-1, r-2)) .$$ Since $D \leq n/(r-1)$, Facts~\ref{turanbound} and~\ref{difffact} imply that \begin{align*} D+e(\overline{T}(n-D-1, r-2)) & \geq D+ \frac{(n-D-1)^2}{2(r-2)}-\frac{(n-D-1)}{2} \\ & \geq \frac{n}{r-1}+\frac{1}{2(r-2)}\left[ \frac{(r-2)}{r-1}n- 1 \right] ^2-\frac{1}{2}\left[\frac{(r-2)}{r-1}n- 1\right] \\ & \geq \frac{(r-2)}{2(r-1)^2} n^2 -\frac{(r-2)}{2(r-1)}n. \end{align*} Thus, it suffices to show that \begin{align}\label{target} \frac{(r-2)}{2(r-1)^2} n -\frac{r-2}{2(r-1)} \geq \frac{n}{2r^2}+\frac{1}{2r}. \end{align} Notice that \begin{align}\label{lemhelp} \frac{r-2}{2(r-1)^2} -\frac{1}{2r^2} =\frac{(r-2)r^2-(r-1)^2}{2r^2(r-1)^2}=\frac{r^3-3r^2+2r-1}{2r^2(r-1)^2} \end{align} and $$\frac{r-2}{2(r-1)}+\frac{1}{2r}=\frac{r^2-r-1}{2r(r-1)}.$$ Since $n \geq 2r$, (\ref{target}) implies that it suffices to show that \begin{align}\label{target2} \frac{r^3-3r^2+2r-1}{r(r-1)^2} -\frac{r^2-r-1}{2r(r-1)}\geq 0. \end{align} Note that $r^3\geq 4r^2-4r+3$ as $r\geq 3$. Thus, $2(r^3-3r^2+2r-1)\geq (r^2-r-1)(r-1)$. So indeed (\ref{target2}) is satisfied, as desired. \endproof \medskip \noindent {\bf Proof of Lemma~\ref{case3prop}.} We need to show that, for all $D \in \mathbb N$ such that $n/r \leq D < (n+r)/(r-1)$, $$\frac{n^2}{2r^2}+\frac{n}{2r} =\binom{n/r+1}{2} \leq D+e(\overline{T}(n-D-1, r-2)) .$$ Since $D<(n+r)/(r-1)$ we have that $D\leq n/(r-1)+1$. So Facts~\ref{turanbound} and~\ref{difffact} imply that \begin{align*} D+e(\overline{T}(n-D-1, r-2)) & \geq D+ \frac{(n-D-1)^2}{2(r-2)}-\frac{(n-D-1)}{2} \\ & \geq \frac{n}{r-1}+1+ \frac{1}{2(r-2)}\left[ \frac{(r-2)}{r-1}n- 2 \right] ^2-\frac{1}{2}\left[\frac{(r-2)}{r-1}n- 2\right] \\ & \geq \frac{(r-2)}{2(r-1)^2} n^2 -\frac{(r-2)}{2(r-1)}n- \frac{n}{r-1}. \end{align*} Thus, it suffices to show that \begin{align}\label{targety} \frac{(r-2)}{2(r-1)^2} n -\frac{(r-2)}{2(r-1)}-\frac{1}{r-1} \geq \frac{n}{2r^2}+\frac{1}{2r}. \end{align} Notice that $$\frac{r-2}{2(r-1)}+\frac{1}{r-1}+\frac{1}{2r}=\frac{r^2+r-1}{2r(r-1)}.$$ Since $n\geq 3r$, (\ref{lemhelp}) and (\ref{targety}) imply that it suffices to show that \begin{align}\label{targety2} \frac{3(r^3-3r^2+2r-1)}{2r(r-1)^2} -\frac{r^2+r-1}{2r(r-1)}\geq 0. \end{align} Note that $2r^3-9r^2+8r-4 \geq 0$ as $r\geq 4$. Thus, $3(r^3-3r^2+2r-1)\geq (r^2+r-1)(r-1)$. So indeed (\ref{targety2}) is satisfied, as desired. \endproof \end{document}