# A Proof of the $(n,k,t)$ Conjectures

Stacie Baumann  Department of Mathematics and Statistics, Auburn University
AL, USA<EMAIL_ADDRESS>and  Joseph Briggs  Department of Mathematics and
Statistics, Auburn University
AL, USA<EMAIL_ADDRESS>
###### Abstract.

An _$(n,k,t)$ -graph_ is a graph on $n$ vertices in which every set of $k$
vertices contain a clique on $t$ vertices. Turán’s Theorem (complemented)
states that the unique minimum $(n,k,2)$-graph is a disjoint union of cliques.
We prove that minimum $(n,k,t)$-graphs are always disjoint unions of cliques
for any $t$ (despite nonuniqueness of extremal examples), thereby generalizing
Turán’s Theorem and confirming two conjectures of Hoffman et al.

Keywords. Extremal Graph Theory, Turán’s Theorem, $(n,k,t)$ Conjectures

Mathematics Subject Classification. 05C35

##  1\. Introduction

The protagonists of this paper are $(n,k,t)$-graphs. Throughout this paper, it
is assumed $n,k,t$ and $r$ are positive integers and $n\geq k\geq t$.

######  Definition 1.1.

A graph $G$ is an $(n,k,t)$-_graph_ if $|V(G)|=n$ and every induced subgraph
on $k$ vertices contains a clique on $t$ vertices. A _minimum_ $(n,k,t)$-graph
is an $(n,k,t)$-graph with the minimum number of edges among all
$(n,k,t)$-graphs.

The study of the minimum number of edges in an $(n,k,t)$-graph, and so
implicitly the structure of minimum $(n,k,t)$-graphs, is a natural extremal
graph theory problem-as we will see shortly, this setting generalizes the
flagship theorems of Mantel and Turán. In [11] the following were conjectured.

######  Conjecture 1.2 (The Weak $(n,k,t)$-Conjecture).

There exists a minimum $(n,k,t)$-graph that is a disjoint union of cliques.

######  Conjecture 1.3 (The Strong $(n,k,t)$-Conjecture).

All minimum $(n,k,t)$-graphs are a disjoint union of cliques.

Note that throughout this paper “disjoint union” refers to a _vertex_
-disjoint union, and a disjoint union of cliques allows isolated vertices
(namely cliques of size 1).

We prove the following theorem, confirming the Strong (and therefore also the
Weak) $(n,k,t)$-Conjecture.

######  Theorem 1.4.

All minimum $(n,k,t)$-graphs are a disjoint union of cliques.

We prove Theorem 1.4 by proving a stronger statement involving the
independence number of the graph (see Theorem 3.6).

##  2\. Previous Results

Given graphs $G$ and $H$, let $\overline{G}$ denote the complement of $G$, let
$G+H$ denote the disjoint union of $G$ and $H$, and for a positive integer $s$
let $sG=G+\dots+G$ ($s$ times). The authors in [11] discussed the following
basic cases of the Strong $(n,k,t)$-Conjecture.

  * •

$t=1$. Every graph on $n$ vertices is an $(n,k,1)$-graph, so the unique
minimum $(n,k,1)$-graph is $nK_{1}$.

  * •

$k=t\geq 2$. The unique minimum $(n,k,k)$-graph is $K_{n}$.

  * •

$n=k$. The unique minimum $(n,n,t)$-graph is $(n-t)K_{1}+K_{t}$.

When $t=2$, the strong $(n,k,t)$-conjecture is equivalent to Turán’s Theorem,
which we recall here. If $r\leq n$ are positive integers let
$T_{n,r}=\overline{K_{p_{1}}+\dots+K_{p_{r}}}$ where $p_{1}\leq
p_{2}\leq\dots\leq p_{r}\leq p_{1}+1$ and $p_{1}+p_{2}\dots+p_{r}=n$
($T_{n,r}$ is called the _Turán Graph_). That is to say, $\overline{T}_{n,r}$
is a disjoint union of $r$ cliques where the number of vertices in each clique
differs by at most one. Turán’s Theorem will be used frequently throughout
this paper. The complement of the traditional statement is below.

######  Theorem 2.1 (Turán’s Theorem).

The unique graph on $n$ vertices without an independent set of size $r+1$ with
the minimum number of edges is $\overline{T}_{n,r}$.

By Turán’s Theorem, the unique minimum $(n,k,2)$-graph is
$\overline{T}_{n,k-1}$. Indeed, the fact that Turán’s Theorem (this version)
depends on the independence number of a graph inspired the proof of the main
theorem.

Arguably the most famous research direction in extremal graph theory is study
of Turán numbers, that is, for a fixed graph $F$ and the class
$\text{Forb}_{n}(F)$ of $n$-vertex graphs not containing a copy of $F$, what
is the maximum number of edges? Turán’s Theorem gives an exact answer when $F$
is complete. Denoting $\chi(F)$ for the chromatic number of $F$, the classical
Erdős-Stone Theorem [7] gives an asymptotic answer of
$(1-1/(\chi(F)-1))\binom{n}{2}$ for nonbipartite $F$ as $n\rightarrow\infty$,
and the bipartite $F$ case is still a very active area of research (see eg
[2], [9]). A more general question considers a family $\mathcal{F}$ of graphs
and the collection $\text{Forb}_{n}(\mathcal{F})$ of all $n$-vertex graphs not
containing any subgraph in $\mathcal{F}$. In this language, an $(n,k,t)$-graph
is precisely a complement of a graph in $\text{Forb}_{n}(\mathcal{F})$, where
$\mathcal{F}$ is the family of $k$-vertex graphs $F$ where $\bar{F}$ does not
contain $K_{t}$. Note that this $\mathcal{F}$ almost always has
$\max_{F\in\mathcal{F}}\\{\chi(F)\\}>2$, meaning the Erdős-Stone Theorem
determines the correct edge density for large $n$. But Theorem 3.6 is still
interesting for 2 reasons:

  * •

The values of $k$ and $t$ are arbitrary, not fixed (and may grow with $n$),
and

  * •

This result is exact, not asymptotic.

There has been some previous work towards the proof of the conjectures. In
[14], the Strong $(n,k,t)$-Conjecture was proved for $n\geq k\geq t\geq 3$ and
$k\leq 2t-2$, utilizing an extremal result about vertex covers attributed by
Hajnal [10] to Erdős and Gallai [6]. In [11], for all $n\geq k\geq t$, the
structure of minimum $(n,k,t)$-graphs that are disjoint union of cliques was
described more precisely as follows.

######  Theorem 2.2 ([11]).

Suppose $G$ has the minimum number of edges of all $(n,k,t)$-graphs that are a
disjoint union of cliques. Then $G=aK_{1}+\overline{T}_{n-a,b}$, for some
$a,b$ satisfying

$a+b(t-1)=k-1,$

and

$b\leq\min\left(\left\lfloor\frac{k-1}{t-1}\right\rfloor,n-k+1)\right).$

The following example shows Theorem 1.4 cannot be strengthened to include
uniqueness (and in particular the choice of $b$ above need not be unique).

######  Example 2.3.

Theorem 2.2 tells us the graphs with the minimum number of edges of all
$(10,8,3)$-graphs that are a disjoint union of cliques are among
$5K_{1}+\overline{T}_{5,1}=5K_{1}+K_{5}$,
$3K_{1}+\overline{T}_{7,2}=3K_{1}+K_{3}+K_{4}$, or
$K_{1}+\overline{T}_{9,3}=K_{1}+3K_{3}$ (as given by $b=1,2,3$ in the above).
These graphs have $10$, $9$, and $9$ edges respectively. So,
$3K_{1}+\overline{T}_{7,2}=3K_{1}+K_{3}+K_{4}$ and
$K_{1}+\overline{T}_{9,3}=K_{1}+3K_{3}$ both have the minimum number of edges
of all $(10,8,3)$-graphs among disjoint unions of cliques.

Hoffman and Pavlis [12] have found for any positive integer $N$ there exist
some $n\geq k\geq 3$ with at least $N$ non-isomorphic $(n,k,3)$-graphs which
are minimum (among graphs which are disjoint unions of cliques, although
Theorem 3.6 now removes this restriction). Further, Allen et al. [1]
determined precisely the values of $b$ from Theorem 2.2 that minimize the
number of edges. This was somehow off-putting, but Observation 2.5 puts such
concerns to rest (and may be the reason why the problem still remains
tractable). Notice that the independence number of the graphs in Example 2.3
are $6$, $5$, and $4$ respectively. These lead to Observation 2.5, but first
we state the following observation that will be used in the proof of
Observation 2.5 and frequently throughout the remainder of the paper. Let
$c(G)$ denote the number of connected components of a graph $G$, and let
$\alpha(G)$ denote its independence number.

######  Observation 2.4.

Suppose $G$ is a disjoint union of cliques. Then $\alpha(G)=c(G)$.

The following observation inspired considering the independence number in the
main proof.

######  Observation 2.5.

Suppose $G_{1}$ and $G_{2}$ are disjoint union of clique graphs that are both
minimum $(n,k,t)$-graphs. Then $\alpha(G_{1})\neq\alpha(G_{2})$.

###### Proof.

If $t=2$, then $G_{1}=G_{2}$ by uniqueness in Turán’s Theorem. So assume
$t>2$. For a contradiction, suppose $\alpha(G_{1})=\alpha(G_{2})$. By Theorem
2.2, there exist positive integers $a_{1},b_{1},a_{2},b_{2}$, such that
$G_{i}=a_{i}K_{1}+\overline{T}_{n-a_{i},b_{i}}$ and $a_{i}+b_{i}(t-1)=k-1$
(for $i=1,2$). Thus, $a_{1}+b_{1}(t-1)=a_{2}+b_{2}(t-1)$. Also, by Observation
2.4, $a_{1}+b_{1}=a_{2}+b_{2}$. Hence $b_{1}-b_{1}(t-1)=b_{2}-b_{2}(t-1)$.
Combining these and noting $t>2$ gives $b_{1}=b_{2}$ and $a_{1}=a_{2}$. ∎

##  3\. The Proof

We collect together some preliminary lemmas. Firstly, because we will use
induction on $t$ in Theorem 3.6, we observe that $(n,k,t)$-graphs contain
$(n^{\prime},k^{\prime},t^{\prime})$-graphs for certain smaller values of
$n^{\prime}$, $k^{\prime}$, and $t^{\prime}$. Given a set $X\subseteq V(G)$,
let $G[X]$ denote the subgraph of $G$ induced by the vertices in $X$ and let
$G-X=G[V(G)\setminus X]$.

######  Lemma 3.1.

If $G$ is an $(n,k,t)$-graph and $S\subseteq V(G)$ is an independent set, then
$G-S$ is an $(n-|S|,k-|S|,t-1)$-graph.

###### Proof.

Clearly $|V(G-S)|=n-|S|$. Let $X$ be a subset of $V(G-S)$ with $|X|=k-|S|$.
Because $G$ is an $(n,k,t)$-graph, $G[S\cup X]$ contains a $K_{t}$. Because
$S$ is an independent set, at most $1$ vertex in this $K_{t}$ was from $S$.
Thus, $(G-S)[X]$ must contain a $K_{t-1}$. ∎

Because Theorem 3.6 considers the independence number of $(n,k,t)$-graphs, we
now enrich the $(n,k,t)$ notation to include the independence number.

######  Definition 3.2.

A graph $G$ is an $(n,k,t,r)$-_graph_ if $G$ is an $(n,k,t)$-graph, and
$\alpha(G)=r$. A _minimum_ $(n,k,t,r)$-graph is an $(n,k,t,r)$-graph with the
minimum number of edges among all $(n,k,t,r)$-graphs.

The following lemma determines an upper bound for the independence number of
an $(n,k,t)$-graph.

######  Lemma 3.3.

If $G$ is an $(n,k,t)$-graph, then $\alpha(G)<k-t+2$.

###### Proof.

For a contradiction, suppose $G$ has an independent set, call it $S$, of size
$k-t+2$. Let $X^{\prime}$ be any $t-2$ vertices in $G-S$ (this is possible
because $|V(G-S)|=n-(k-t+2)=(n-k)+t-2\geq t-2$). Define $X\coloneqq S\cup
X^{\prime}$, so $|X|=k$. Then there exists a $K_{t}$ in $G[X]$ which
necessarily contains $2$ vertices in $S$. This is a contradiction because $S$
is independent. Thus $\alpha(G)<k-t+2$. ∎

But, subject to this bound, all independence numbers $\alpha(G)$ are
attainable. Indeed, for any $1\leq r\leq k-t+1$ the graph
$(r-1)K_{1}+K_{n-r+1}$ is an example of an $(n,k,t,r)$-graph.

Below is an observation about minimum $(n,k,t)$-graphs. It will be used in in
the proof of Theorem 3.6.

######  Lemma 3.4.

Suppose $k>t$ and let $a\leq n$ be a positive integer. Let $H$ be an
$(n,k,t)$-graph with the minimum number of edges among $(n,k,t)$-graphs with
independence number at most $a$. If $\alpha(H)<a$, then $H$ is not an
$(n,k-1,t)$-graph.

###### Proof.

Among all $(n,k,t)$-graphs with independence number at most $a$, suppose $H$
has the fewest edges. For a contradiction suppose $\alpha(H)<a$ and $H$ is an
$(n,k-1,t)$-graph. Because $\alpha(H)<a\leq n$, there exists an edge, $e$ in
$H$. Let $H^{-}$ be the graph formed from $H$ by deleting $e$ and let $v\in
e$. Let $X$ be a subset of $V(H^{-})$ with $|X|=k$. If $X$ does not contain
$v$, then $H^{-}[X]=H[X]$ contains a $K_{t}$. So, suppose $X$ contains $v$.
Then $|X\setminus\\{v\\}|=k-1$. Because $H$ is an $(n,k-1,t)$-graph,
$H[X\setminus\\{v\\}]=H^{-}[X\setminus\\{v\\}]$ contains a $K_{t}$. So
$H^{-}[X]$ contains a $K_{t}$. Also, $H^{-}$ has independence number at most
$1$ greater than $H$. Thus, $H^{-}$ is an $(n,k,t)$-graph with fewer edges
than $H$ and $\alpha(H^{-})\leq a$, contradicting minimality of $H$. ∎

We caution that Lemma 3.4 is not necessarily true when $\alpha(H)=a$. For
example, the minimum $(8,8,4)$-graph, $H$, with independence number
$\alpha(H)\leq a:=2$ is $K_{4}+K_{4}$. Despite this, $K_{4}+K_{4}$ is also an
$(8,7,4)$-graph.

Finally, since we will be using the $(n,k,t)$ condition to build the desired
disjoint union of cliques, it is useful to keep track of the size of their
largest $K_{t}$-free subgraph.

######  Lemma 3.5.

Suppose $\Gamma$ is a graph which is a disjoint union of cliques. Denote by
$A_{\Gamma}$ the subgraph consisting of cliques with $<t$ vertices, and
$B_{\Gamma}$ the subgraph of components with $\geq t$ vertices (so that
$\Gamma=A_{\Gamma}+B_{\Gamma}$). Then:

  1. a.

the largest $K_{t}$-free subgraph of $\Gamma$ has
$(t-1)c(B_{\Gamma})+|V(A_{\Gamma})|$ vertices,

  2. b.

if also $\Gamma$ is an $(n,k,t)$-graph, then

$k-1\geq(t-1)c(B_{\Gamma})+|V(A_{\Gamma})|,\hskip 14.22636pt\text{ and}$

  3. c.

if furthermore $\Gamma$ is _not_ an $(n,k-1,t)$-graph, the above inequality is
an equality.

###### Proof.

The largest subgraph $F$ of $\Gamma$ with no $K_{t}$ is obtained by starting
with $A_{\Gamma}$ and adding $t-1$ vertices from each clique of $B_{\Gamma}$ .
So $|V(F)|=(t-1)c(B_{\Gamma})+|V(A_{\Gamma})|$. If $\Gamma$ is an
$(n,k,t)$-graph, then $F$ has at most $k-1$ vertices in total. If $\Gamma$ is
not an $(n,k-1,t)$-graph, then there is some $(k-1)$-set of vertices without a
$K_{t}$, and as $F$ is the largest, it follows $|V(F)|\geq k-1$ so we have
equality. ∎

We now proceed with the proof of the main theorem.

######  Theorem 3.6.

Every minimum $(n,k,t,r)$-graph is a disjoint union of cliques.

###### Proof.

The proof proceeds by induction on $t$. If $t=1$, then every graph on $n$
vertices is an $(n,k,1)$-graph because all sets of $k$ vertices contain a
$K_{1}$. Thus, the unique minimum $(n,k,1,r)$-graph is $\overline{T}_{n,r}$ by
Turán’s Theorem. Else, $t\geq 2$.

Suppose $r\geq k-t+2$. By Lemma 3.3, there does not exist an
$(n,k,t,r)$-graph. So the theorem holds vacuously.

Next suppose $r<\frac{k}{t-1}$. By Turán’s Theorem, $\overline{T}_{n,r}$ is
the unique graph with independence number $r$ and the minimum number of edges.
So it suffices to check that $\overline{T}_{n,r}$ is genuinely an
$(n,k,t)$-graph. Let $X$ be a subset of $V(\overline{T}_{n,r})$ with $|X|=k$.
By the pigeonhole principle, $X$ contains at least $\frac{k}{r}>t-1$ vertices
from one connected component of $\overline{T}_{n,r}$. Because all connected
components of $\overline{T}_{n,r}$ are cliques, $\overline{T}_{n,r}[X]$
contains a $K_{t}$. Therefore $\overline{T}_{n,r}$ is the unique minimum
$(n,k,t,r)$-graph.

So suppose instead $\frac{k}{t-1}\leq r<k-t+2$. Let $G$ be an
$(n,k,t,r)$-graph. We first construct an $(n,k,t,r)$-graph $G^{\prime}$ that
is a disjoint union of cliques with $E(G)\geq E(G^{\prime})$. Let $S$ be an
independent set in $G$ with $|S|=r$. Then $\alpha(G-S)\leq\alpha(G)=r$. By
Lemma 3.1, $G-S$ must be an $(n-r,k-r,t-1)$-graph. Let $H$ be any minimum
$(n-r,k-r,t-1)$-graph with $\alpha(H)\leq r$, so that $|E(G-S)|\geq|E(H)|$. By
the induction hypothesis, $H$ is a disjoint union of cliques with
$\alpha(H)\leq r$. So, by Observation 2.4, $c(H)\leq r$. Let $G^{\prime}$ be
the graph formed by joining one distinct vertex to each clique component of
$H$ and adding $r-c(H)$ new isolated vertices

$|S|=r$Some$(n-r,k-r,t-1)$-graph | $c(H)$$r-c(H)$$H$$A_{H}$$A_{G^{\prime}}$$B_{H}$$B_{G^{\prime}}$
---|---
$G$ | $G^{\prime}$
Figure 1.

(see Figure 1). Thus, $c(G^{\prime})=c(H)+(r-c(H))=r$. So, $G^{\prime}$ is
also a disjoint union of cliques and, by Observation 2.4,
$\alpha(G^{\prime})=r$. Each vertex in $V(G-S)$ must be adjacent to at least
one vertex in $S$, else there is an independent set in $G$ with more than $r$
vertices. Also, by construction of $G^{\prime}$, each vertex in $H$ has
exactly $1$ edge to the vertices in $G^{\prime}-H$. So,

(1) $\begin{split}|E(G)|&=|E(G-S)|+\sum_{v\in V(G-S)}|E(v,S)|\\\
&\geq|E(H)|+\sum_{v\in V(G-S)}1\\\ &=|E(H)|+\sum_{v\in
V(H)}|E(v,V(G^{\prime}-H))|\\\ &=|E(G^{\prime})|,\\\ \end{split}$

where $E(v,W)$ denotes the set of edges between $v$ and $W$.

We now show $G^{\prime}$ is an $(n,k,t,r)$-graph. First, let $A_{H}$ be the
subgraph of $H$ consisting of connected components (necessarily cliques) with
strictly less than $t-1$ vertices and $B_{H}$ be the subgraph of $H$
consisting of components with at least $t-1$ vertices. Lemma 3.5 (b) applied
to the $(n-r,k-r,t-1)$-graph $H$ gives

(2) $k-r>(t-2)c(B_{H})+|V(A_{H})|.$

Now let $A_{G^{\prime}}$ be the subgraph of $G^{\prime}$ consisting of
connected components (by construction of $G^{\prime}$, necessarily cliques)
with strictly less than $t$ vertices and $B_{G^{\prime}}$ be the subgraph of
$G^{\prime}$ consisting of components (necessarily cliques) with at least $t$
vertices. Then:

  * •

$c(B_{G^{\prime}})=c(B_{H})$, as every clique of size $\geq t-1$ in $H$ has
become a clique of size $\geq t$ in $G^{\prime}$ (by construction of
$G^{\prime}$); and

  * •

$|V(A_{G^{\prime}})|=|V(A_{H})|+r-c(B_{H})$, as every clique of size $<t-1$ in
$H$ has become a clique of size $<t$ in $G^{\prime}$, and only $c(B_{H})$ of
the $r$ vertices in $G^{\prime}-H$ are not added to the larger $B_{H}$
components.

Let $X$ be a subset of $V(G^{\prime})$ with $|X|=k$. By definition of
$G^{\prime}$, at most $|V(A_{G^{\prime}})|=|V(A_{H})|+r-c(B_{H})$ vertices in
$X$ are in components with less than $t$ vertices. Thus, by the pigeonhole
principle, some component of $B_{G^{\prime}}$ contains at least
$\frac{k-|V(A_{G^{\prime}})|}{c(B_{G^{\prime}})}$ vertices from $X$. Plus, we
can lower bound

$\displaystyle\frac{k-|V(A_{G^{\prime}})|}{c(B_{G^{\prime}})}$
$\displaystyle=\frac{k-(|V(A_{H})|+r-c(B_{H}))}{c(B_{H})}$
$\displaystyle=\frac{k-|V(A_{H})|-r}{c(B_{H})}+1$ $\displaystyle>(t-2)+1$ (By
(2)) $\displaystyle=t-1.$

Thus, $G^{\prime}[X]$ contains a $K_{t}$. This proves $G^{\prime}$ is an
$(n,k,t,r)$-graph. So, we have found an $(n,k,t,r)$-graph $G^{\prime}$ which
is a disjoint union of cliques and with $|E(G)|\geq|E(G^{\prime})|$ (as needed
for the weak $(n,k,t)$-conjecture).

Now, suppose $G$ is also a minimum $(n,k,t,r)$-graph. So the inequality in (1)
is actually an equality. Thus, each vertex $v\in G-S$ is adjacent to exactly
one vertex in $S$. Also, $|E(G-S)|=|E(H)|$, so $G-S$ is a minimum
$(n-r,k-r,t-1)$ graph with independence number at most $r$ and is therefore
also a disjoint union of cliques by the induction hypothesis.

We show $G$ must also be a disjoint union of cliques. This will be implied by
the following two additional facts.

  * $(\diamondsuit)$

If $u$,$v$ are two vertices in different components of $G-S$, then they cannot
be adjacent to the same vertex $w\in S$.

  * $(\heartsuit)$

If $u$,$v$ are two vertices in the same components of $G-S$, then they are
adjacent to the same vertex in $S$.

To prove $(\diamondsuit)$, note that if $u$ and $v$ are two vertices in the
different components of $G-S$ then they cannot be adjacent to the same vertex
$w\in S$, for otherwise $S\setminus\\{w\\}\cup\\{u,v\\}$ is an independent set
in $G$ with $r+1$ vertices.

We now prove $(\heartsuit)$. Similarly to before, define $A_{G-S}$ to be the
subgraph of $G-S$ consisting of connected components with strictly less than
$t-1$ vertices and $B_{G-S}$ the subgraph of $G-S$ consisting of components
with at least $t-1$ vertices. For a contradiction, suppose $u$ and $v$ are two
vertices in the same component, $F$, of $G-S$ and they are adjacent to two
distinct vertices in $S$. Because of $(\diamondsuit)$ and the vertices in
component $F$ are adjacent to at least $2$ distinct vertices in $S$,
$c(G-S)<|S|=r$. This leads to two important facts:

  1. (i)

By Observation 2.4, $\alpha(G-S)<r$.

  2. (ii)

$A_{G-S}$ contains only isolated vertices (else choose a vertex in $A_{G-S}$
with at least one incident edge and delete all such. This is still an
$(n-r,k-r,t-1)$-graph with independence number at most $r$, and strictly fewer
edges than $G-S$, contradicting minimality). In particular, as $|F|\geq 2$,
$F$ must be a component of $B_{G-S}$.

Let $Y$ be the union of subsets of $t-2$ vertices from each connected
component of $B_{G-S}-V(F)$. Therefore, $|Y|=(t-2)(C(B_{G-S})-1)$. Let $Z$ be
a set of $t-3$ vertices in $V(F)-\\{u,v\\}$ (this is possible because of
(ii)). Define

$X^{\prime}=S\cup V(A_{G-S})\cup Y\cup Z\cup\\{u,v\\}.$

We now show $|X^{\prime}|=k$. Consider two cases. Suppose $k-r>t-1$. Because
$G-S$ is an $(n-r,k-r,t-1)$-graph, using (i) and Lemma 3.4 shows $G-S$ is not
an $(n-r,k-r-1,t-1)$-graph. So Lemma 3.5 (c) gives

(3) $k-r-1=|V(A_{G-S})|+(t-2)c(B_{G-S}).$

Now, suppose $k-r=t-1$. Then, $G-S=K_{n-r}$, so $|V(A_{G-S})|=0$ and $c(B)=1$.
Therefore, Equation (3) holds for all $k-r\geq t-1$. Thus, in either case,

$\begin{array}[]{llr}|X^{\prime}|&\lx@intercol=r+|V(A_{G-S})|+(t-2)(c(B_{G-S})-1)+(t-3)+2\hfil\lx@intercol\\\
&=r+(k-r-1)+1&\text{ (By \eqref{largestset})}\\\ &=k.&\\\ \end{array}$

Any clique of size $t$ in $G[X^{\prime}]$ may contain at most $1$ vertex from
$S$ since $S$ is an independent set. Thus, if $G[X^{\prime}]$ contains at
$K_{t}$, then at least $t-1$ vertices in $X^{\prime}$ must be in the same
connected component of $G[V(A_{G-S})\cup Y\cup Z\cup\\{u,v\\}]$. The set
$X^{\prime}$ does not contain $t-1$ vertices from the same connected
components in $A_{G-S}$ or $Y$. The set $X^{\prime}$ contains $t-1$ vertices
from $V(F)$ (namely, $Z\cup\\{u,v\\}$), but because each vertex in $V(F)$ is
adjacent to exactly $1$ vertex in $S$ and $u$ and $v$ are adjacent to two
unique vertices in $S$, $u$ and $v$ are not in a clique on $t$ vertices in
$G[X^{\prime}]$. Thus, $G[X^{\prime}]$ does not contain a clique on $t$
vertices, contradicting $G$ being an $(n,k,t)$-graph. ∎

Theorem 3.6 implies Theorem 1.4 proving the $(n,k,t)$-conjectures. Indeed, a
minimum $(n,k,t)$-graph is one with the minimum number of edges among all
minimum $(n,k,t,r)$-graphs for $1\leq r<k-t+2$.

Note, even if we relax the definition of an $(n,k,t,r)$-graph and let $n$,
$k$, and $t$ be any positive integers, Theorem 3.6 still holds. If $k>n$ then
there does not exist a set of $k$ vertices, so all graphs on $n$ vertices are
$(n,k,t,r)$-graphs. Thus, the unique minimum $(n,k,t,r)$-graph is
$\overline{T}_{n,r}$ by Turán’s Theorem. Also, if $n\geq k$ and $t>k$, then an
induced subgraph on $k$ vertices cannot contain a clique on $t$ vertices, so
no graphs are $(n,k,t,r)$-graphs. So, the theorem holds vacuously.

In light of Observation 2.5, one might be led to believe for every positive
integer $r$, there exists a unique minimum $(n,k,t,r)$-graph. However, this is
not the case.

######  Observation 3.7.

There exist $n,k,t,$ and $r$ for which the minimum $(n,k,t,r)$-graph is not
unique.

For example, $2K_{2}+K_{5}$ and $K_{1}+2K_{4}$ are both minimum
$(9,8,4,3)$-graphs. These can each be formed as described in the proof of
Theorem 3.6 by letting $G-S$ be the minimum $(6,5,3)$-graphs, $2K_{1}+K_{4}$
or $K_{3}+K_{3}$, respectively. However, by Observation 2.5 each minimum
$(n,k,t)$-graph has a unique independence number. In this example, by Theorem
2.2 and Theorem 1.4, the minimum $(9,8,4)$-graph is $4K_{1}+K_{5}$ and this is
the unique minimum $(9,8,4,5)$-graph.

##  4\. Future Directions

Our main result and [1] together solve the extremal problem of finding the
minimum number of edges in an $(n,k,t)$-graph. Viewing edges as cliques on $2$
vertices leads to one possible generalization of this problem.

######  Question 4.1.

Let $s$ be a positive integer. What is the minimum number of cliques on $s$
vertices in an $(n,k,t)$-graph?

A logical first step may be to ask: What is the minimum number of cliques on
$s$ vertices in an $(n,k,2)$-graph? Recall, when $s=2$, this is equivalent to
Turán’s Theorem. For general $s$, it turns out this is a special case of a
question asked by Erdős [4]. He conjectured that a disjoint union of cliques
would always be best. However, Nikiforov [13] disproved this conjecture,
observing that a clique-blowup of $C_{5}$ has independence number $2$ (so is
an $(n,3,2)$-graph), but has fewer cliques on $4$ vertices than
$2K_{\frac{n}{2}}$–the graph which has fewest $K_{4}$’s among all
$(n,3,2)$-graphs that are a disjoint union of cliques. Das et al. [3] and
Pikhurko [15] independently found the minimum number of cliques on $4$
vertices in an $(n,3,2)$-graph for $n$ sufficiently large and Pikhurko [15]
found the minimum number of cliques on $5$ vertices, cliques on $6$ vertices,
and cliques on $7$ vertices in an $(n,3,2)$-graph for $n$ sufficiently large.
But their approaches are non-elementary and rely heavily on Razborov’s flag
algebra method. A summary on related results can be found in Razborov’s survey
[16].

In [14], Noble et al. showed for $n\geq k\geq t\geq 3$ and $k\leq 2t-2$ every
$(n,k,t)$-graph must contain a $K_{n-k+t}$. Because $(k-t)K_{1}+K_{n-k+t}$ is
an $(n,k,t)$-graph, this shows for $n\geq k\geq t\geq 3$ and $k\leq 2t-2$ the
minimum number of $s$-cliques an $(n,k,t)$-graph must contain is
${n-k+t\choose s}$ (noting ${n-k+t\choose s}=0$ if $s>n-k+t$).

Thus, the smallest interesting open question of this form is as follows:

######  Question 4.2.

What is the minimum possible number of triangles in an $(n,5,3)$-graph?

We can also consider the other end of the spectrum. What is the minimum number
of cliques on $t$ vertices in an $(n,k,t)$-graph? Also, for what values of
$n$, $k$, and $t$ does an $(n,k,t)$-graph necessarily contain at least one
clique of $t+1$ vertices?

Similar to Question 4.1, one could ask: What is the minimum number $n$ that an
$(n,k,t)$-graph must contain a clique on $s$ vertices? However, if $t=2$, this
is exactly the Ramsey number $R(k,s)$. Thus, this question seems very hard in
general.

One other common direction to take known results in extremal graph theory
where extremal structures have been identified, is to ask whether every _near-
optimal_ example can be modified to make the optimal example using relatively
few edits. For example, a result of Füredi [8], when complemented, gives the
following strengthening of Turán’s Theorem:

######  Theorem 4.3.

Let $G$ be an $n$-vertex graph without an independent set of size $r+1$ with
$|E(G)|\leq|E(\overline{T}_{n,r})|+q$. Then, upon adding at most $q$
additional edges, $G$ contains a spanning vertex-disjoint union of at most $r$
cliques.

Fixing an independence number $r$ and writing $G^{\prime}$ for a minimum
$(n,k,t,r)$-graph (as in Theorem 3.6), this leads us to the following
question:

######  Question 4.4.

Suppose $G$ is an $(n,k,t)$-graph with independence number $r$, satisfying
$|E(G)|\leq|E(G^{\prime})|+q$. Does there exist a function $f(q)$ such that
only $f(q)$ edges need adding to make $G$ contain a spanning disjoint union of
$\leq r$ cliques?

One would need the function $f(q)$ to be independent of $n$ in order for the
above to be interesting. Does $f$ need to depend on $k$? Or on $t$? Theorem
4.3 suggests that the answer to the first question may actually be no.

Finally, in light of the constructive nature of the proof of Theorem 3.6, one
may ask whether every _inclusion-minimal_ $(n,k,t)$-graph (that is, an
$(n,k,t)$-graph which is no longer $(n,k,t)$ upon the removal of any edge) is
necessarily a disjoint union of cliques. But, there are counterexamples to
this even in the original setting of Turán’s theorem ($t=2$). For example,
$C_{5}$ is an inclusion-minimal $(5,3,2)$-graph, but contains neither of the
inclusion-minimal $(5,3,2)$-graphs which are disjoint unions of cliques
($K_{2}+K_{3}$ and $K_{1}+K_{4}$).

Since there are inclusion-minimal $(n,k,t)$-graphs which are not disjoint
unions of cliques, this suggests the saturation problem for $(n,k,t)$-graphs
is interesting:

######  Question 4.5.

Among all inclusion-minimal $(n,k,t)$-graphs, what is the maximum possible
number of edges?

The classical saturation result of Zykov [17] and Erdős-Hajnal-Moon [5] (when
complemented) says that when $t=2$, the answer is given by
$(k-2)K_{1}+K_{n-k+2}$. The example above shows there are instances of
inclusion-minimal $(n,k,t)$-graphs that are not disjoint unions of cliques,
but $K_{1}+K_{4}$ still has more edges that $C_{5}$. In general, we conjecture
that the maximum is still always attained by a disjoint union of cliques.

## Acknowledgements

We are indebted to Peter Johnson for introducing us to this problem and
suggestions improving an earlier version of the script, and to Paul Horn for
helpful discussions. The first author would also like to thank Alex Stevens,
Andrew Owens, Calum Buchanan, and the rest of the Masamu Graph Theory Research
Group for thoughtful conversations about the topic.

## References

  * [1] J. Allen, B. Drynan, D. Dunst, Z. Hefty, and E. Smith.  A precise definition of an extremal family.  In preparation.
  * [2] B. Bukh.  Random algebraic construction of extremal graphs.  Bulletin of the London Mathematical Society, 47(6):939–945, 2015\.
  * [3] S. Das, H. Huang, J. Ma, H. Naves, and B. Sudakov.  A problem of erdős on the minimum number of $k$-cliques.  Journal of Combinatorial Theory, Series B, 103(3):344–373, 2013\.
  * [4] P. Erdős.  On the number of complete subgraphs contained in certain graphs.  Magyar Tud. Akad. Mat. Kutató Int. Közl., 7:459–464, 1962\.
  * [5] P. Erdős, A. Hajnal, and J. W. Moon.  A problem in graph theory.  The American Mathematical Monthly, 71(10):1107–1110, 1964.
  * [6] P. Erdos and T. Gallai.  On the minimal number of vertices representing the edges of a graph.  Publ. Math. Inst. Hungar. Acad. Sci, 6(18):1–203, 1961.
  * [7] P. Erdös and A. H. Stone.  On the structure of linear graphs.  Bulletin of the American Mathematical Society, 52(12):1087–1091, 1946.
  * [8] Z. Füredi.  A proof of the stability of extremal graphs, simonovits’ stability from szemerédi’s regularity.  Journal of Combinatorial Theory, Series B, 115:66–71, 2015.
  * [9] Z. Füredi and M. Simonovits.  The history of degenerate (bipartite) extremal graph problems.  In Erdős Centennial, pages 169–264. Springer, 2013.
  * [10] A. Hajnal.  A theorem on $k$-saturated graphs.  Canadian Journal of Mathematics, 17:720–724, 1965.
  * [11] D. Hoffman, P. Johnson, and J. McDonald.  Minimum $(n,k,t)$ clique graphs.  Congr. Numer., 223:199–204, 2015.
  * [12] D. Hoffman and H. Pavlis.  Private communication.
  * [13] V. Nikiforov.  On the minimum number of $k$-cliques in graphs with restricted independence number.  Combinatorics, Probability and Computing, 10(4):361–366, 2001.
  * [14] M. Noble, P. Johnson, D. Hoffman, and J. McDonald.  Application of an extremal result of erdős and gallai to the $(n,k,t)$ problem.  Theory and Applications of Graphs, 4(2):1, 2017.
  * [15] O. Pikhurko and E. R. Vaughan.  Minimum number of $k$-cliques in graphs with bounded independence number.  Combinatorics, Probability and Computing, 22(6):910–934, 2013.
  * [16] A. A. Razborov.  Flag algebras: an interim report.  In The Mathematics of Paul Erdős II, pages 207–232. Springer, 2013.
  * [17] A. A. Zykov.  On some properties of linear complexes.  Matematicheskii sbornik, 66(2):163–188, 1949.