%1 March 1994
% 25 February 1994
% 21 January 1994
\documentstyle[12pt]{article}
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics 1 (1994), \#R2\hfill}
\thispagestyle{empty}
\font\tenmsb=msbm10
\font\sevenmsb=msbm7
\font\fivemsb=msbm5
\newfam\msbfam\textfont\msbfam=\tenmsb\scriptfont\msbfam=\sevenmsb
\def\Bbb#1{\fam\msbfam#1} % blackboard fonts
\newtheorem{thm}{Theorem}
%\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{defn}{Definition}[section]
\newtheorem{ex}{Example}[section]
\newtheorem{prob}{Problem}
\setlength{\textheight}{9.0in}
\setlength{\textwidth}{6.2in}
\addtolength{\topmargin}{-1.0in}
\addtolength{\oddsidemargin}{-0.5in}
\begin{document}
\title{Two Extremal Problems in Graph Theory}
\author{Richard A. Brualdi\thanks{Research partially supported by NSF
Grant DMS-9123318.}\, and Stephen Mellendorf\thanks{Research partially
supported by a Department of Education Fellowship administered by the
University of Wisconsin--Madison.
} \\
Department of Mathematics\\
University of Wisconsin\\
Madison, WI 53706}
\maketitle
\begin{abstract}
We consider the following two problems.
(1) Let $t$ and $n$ be positive integers with $n\geq t\geq 2$. Determine
the maximum number of edges of a graph
of order $n$ that contains neither $K_t$ nor $K_{t,t}$ as a subgraph.
(2) Let $r$, $t$ and $n$ be positive integers with $n\geq rt$ and $t\geq 2$.
Determine the maximum number of edges of a graph
of order $n$ that does not contain $r$ disjoint copies of $K_t$.
Problem 1 for $n<2t$ is solved by Tur\'{a}n's theorem and we
solve it for $n=2t$. We also solve Problem 2 for $n=rt$.
\end{abstract}
\section{Introduction
}
One of the best known results in extremal graph theory is the following
theorem of Tur\'{a}n.
\begin{thm}
\label{th:turan}
Let $t$ and $n$ be positive integers with $n\geq t\geq 2$. Then the maximum
number of edges of a graph of order $n$ that does not contain a
complete subgraph $K_t$ of order $t$ equals
\begin{equation}
\label{eq:turan}
{n\choose 2}- \sum_{i=1}^{t-1} {n_i\choose 2}
\end{equation}
where $n=n_1+\cdots +n_{t-1}$ is a partition of $n$ into $t-1$ parts which
are as
equal as possible. Furthermore, the only graph of order $n$ whose number of
edges equals $(\ref{eq:turan})$ that does not contain a complete subgraph
$K_t$ is the complete $(t-1)$-partite graph $K_{n_1,\ldots,n_{t-1}}$
with parts of sizes $n_1,\ldots,n_{t-1}$, respectively.
\end{thm}
In general, the extremal graph $K_{n_1,\ldots,n_{t-1}}$ in Theorem
\ref{th:turan} contains a complete bipartite subgraph $K_{t,t}$. This
suggests the following problem.
\begin{prob}
\label{problem1}
Let $t$ and $n$ be positive integers with $n\geq t\geq 2$. Determine
the maximum number of edges of a graph
of order $n$ that contains neither $K_t$ nor $K_{t,t}$ as a subgraph.
\end{prob}
If $n<2t$, then Problem \ref{problem1} is equivalent to Tur\'{a}n's theorem.
The case $n=2t$ is settled in the next theorem.
If $G$ and $H$ are graphs, then their {\it sum} is the graph
$G+H$ obtained by taking
disjoint copies of $G$ and $H$ and putting an edge
between each vertex of $G$ and each vertex of $H$. A path of order $n$
is denoted by $P_n$. The complement of a graph $G$ is denoted by
$\overline{G}$.
A connected graph is {\it unicyclic} provided it has a unique
cycle. It follows easily that a
connected graph of order $n$ is unicyclic if and only if it
has exactly $n$ edges.
Recall that a set of vertices of a graph is {\it independent} provided no
two of its vertices are joined by an edge.
If $n$ is an odd integer, then ${\cal H}_n$ denotes the collection of all
unicyclic graphs of order $n$ for which the
maximum cardinality of an independent set equals $(n-1)/2$. Note that
${\cal H}_1$ is empty.
The graphs in ${\cal H}_n$ are characterized in the final section.
\begin{thm}
\label{th:one}
Let $t$ be a positive integer with $t\geq 3$. Then
the maximum number of edges of a graph
of order $2t$ that contains neither $K_t$ nor $K_{t,t}$ as a subgraph equals
\begin{equation}
\label{eq:even}
{2t\choose 2}-\frac{3t}{2}-1\mbox{ if $t$ is even,}
\end{equation}
and equals
\begin{equation}
\label{eq:odd}
{2t\choose 2} -t-4\mbox{ if $t$ is odd.}
\end{equation}
If $t$ is even, then the only graphs of order $2t$ that contain neither
$K_t$ nor $K_{t,t}$ as a subgraph and
whose number of edges equals $(\ref{eq:even})$ are the graphs of the form
$K_{2,\ldots,2}+\overline{H_a}+\overline{H_b}$ where $a$ and $b$ are odd
integers with $a+b=t+2$, $H_a$ is in ${\cal H}_a$
and $H_b$ is in ${\cal H}_b$.
If $t$ is odd, then the only graphs of order $2t$
that contain neither $K_t$ nor $K_{t,t}$ as a subgraph and
whose number of edges equals $(\ref{eq:odd})$ are the graphs of the form
$K_{2,\ldots,2,4}$ and $K_{2,\ldots,2}+U$ where $U$ is
the graph obtained from $K_{3,3}$ by removing an edge, and
the graphs $K_{1,3,3,3}$ and $K_{3,3}+\overline{P_4}$ for $t=5$.
\end{thm}
We prove Theorem \ref{th:one} in the equivalent complementary form stated
in the next theorem.
If $G$ and $H$ are graphs, then their {\it union} is the graph
$G\cup H$ consisting of
disjoint copies of $G$ and $H$. If $m$ is a positive integer, then $mG$
is the graph consisting of $m$ disjoint copies of $G$.
We call a graph {\it bisectable}
provided its vertices can be partitioned into two parts of equal
size such that there are no edges between the two parts.
\begin{thm}
\label{th:onea}
Let $t$ be a positive integer with $t\geq 3$. Then
the minimum number of edges of a graph
of order $2t$ that does not contain an independent set of $t$ vertices
and is not bisectable equals
\begin{equation}
\label{eq:evena}
\frac{3t}{2}+1\mbox{ if $t$ is even,}
\end{equation}
and equals
\begin{equation}
\label{eq:odda}
t+4 \mbox{ if $t$ is odd.}
\end{equation}
If $t$ is even, then the only graphs of order $2t$
that do not contain an independent set of $t$ vertices
and are not bisectable and
whose number of edges equals $(\ref{eq:evena})$ are the graphs of the form
$(t/2-1)K_{2}\cup H_a\cup H_b$ where $a$ and $b$ are odd
integers with $a+b=t+2$, $H_a$ is in ${\cal H}_a$
and $H_b$ is in ${\cal H}_b$.
If $t$ is odd, then the only graphs of order $2t$
that do not contain an independent set of $t$ vertices
and are not bisectable and
whose number of edges equals $(\ref{eq:odda})$ are the graphs
$(t-2)K_{2}\cup K_4$ and $(t-3)K_2\cup W$ where $W$ is
the graph obtained from $K_{3}\cup K_3$ by inserting an additional edge,
and the graphs $K_1\cup 3K_{3}$ and $2K_3\cup P_4$ when $t=5$.
\end{thm}
\begin{prob}
\label{problem2}
Let $r$, $t$ and $n$ be positive integers with $n\geq rt$ and $t\geq 2$.
Determine the maximum number of edges of a graph
of order $n$ that does not contain $r$ disjoint copies of $K_t$.
\end{prob}
If $n$ is sufficiently large, then the solution to Problem \ref{problem2}
is contained in the following theorem of Simonovits \cite{Si} (see also
page 346 of \cite{Bo}).
\begin{thm}
\label{th:simo}
Let $r$, $t$ and $n$ be positive integers with $t\geq 2$ and $n$
sufficiently large. Then the unique graph of order $n$ with the maximum
number of edges that does not contain $r$ disjoint copies of $K_t$ is the
graph $G=K_{r-1}+ H$ where $H=K_{n_1,\ldots,n_{t-1}}$ and
$n-r+1=n_1+\cdots +n_{t-1}$ is a partition of $n-r+1$ into $t-1$ parts as
equal as possible.
\end{thm}
The smallest instance of Problem \ref{problem2} occurs when $n=rt$
and this is settled in the next theorem. By considering complements,
we obtain the following equivalent formulation
of Problem \ref{problem2} in this case: {\it Determine the
minimum number of edges of a graph of order $rt$ that is not $r$-partite
with parts of size $t$}.
\begin{thm}
\label{th:two}
Let $r$ and $t$ be positive integers with $t\geq 2$.
Then the minimum number of edges of a graph
of order $rt$ that is not $r$-partite with parts of size $t$ equals
\begin{equation}
\label{eq:two}
\min\{{r+1\choose 2}, rt-t+1\}=\left\{\begin{array}{ll}
{r+1\choose 2}&\mbox{ if $r\leq 2t-2$}\\
rt-t+1&\mbox{ if $r\geq 2t-2$.}\end{array}\right.
\end{equation}
The only graphs of order $rt$
that are not $r$-partite with parts of size $t$ and whose number of edges
equals $(\ref{eq:two})$ are the graphs of the form
\begin{equation}
\label{eq:cx1}
K_{r+1}\cup (rt-r-1)K_1
\mbox{ for }r\leq 2t-2,
\end{equation}
and the graphs of the form
\begin{equation}
\label{eq:cx2}
K_{1,rt-t+1-p}\cup pK_2\cup (t-2-p)K_1, \; (0\leq p\leq t-2)
\mbox{ for } r\geq 2t-2.
\end{equation}
\end{thm}
In the proof of Theorem \ref{th:two} we shall make use of the following
difficult result of Hajnal and Szemer\'{e}di \cite{HS} (see also
page 351 of \cite{Bo}).
\begin{thm}
\label{th:hs}
Let $r$ and $t$ be positive integers, and let $G$ be a graph of order $rt$
each of whose vertices has degree at most $r-1$. Then $G$ is $r$-partite
with parts of size $t$.
\end{thm}
To conclude this introduction we note that by use of the adjacency matrix,
each of Problems \ref{problem1}
and \ref{problem2} can be formulated in terms of matrices.
If $A$ is a matrix of order $n$ and $\alpha$ and $\beta$ are subsets of
$\{1,2,\ldots,n\}$, then $A[\alpha,\beta]$ is the submatrix of $A$
determined by the rows indexed by $\alpha$ and columns indexed by $\beta$.
Problem \ref{problem1} is equivalent to the following.
\begin{prob}
\label{problem3}
Let $t$ and $n$ be positive integers with $n\geq t\geq 2$. Determine
the minimum number $s(n,t)$ such that every symmetric $(0,1)$-matrix
of order $n$ with $0$'s on the main diagonal and with at least $s(n,t)$
$0$'s above the main diagonal contains a zero submatrix $A[\alpha,\beta]$
of order $t$ where either $\alpha=\beta$ or $\alpha\cap\beta=\emptyset$.
\end{prob}
From Theorem \ref{th:one} we obtain that $s(2t,t)=
{2t\choose 2}-\frac{3t}{2}$ if $t$ is even and $s(2t,t)=
{2t\choose 2} -t-3$ if $t$ is odd.
Problem \ref{problem3} can be viewed as a symmetric version of the
famous problem of Zarankiewicz:
Let $1\leq c\leq a$ and $1\leq
d\leq b$. Determine the minimum number $Z(a,b;c,d)$,
such that each $a\times b$
matrix with $Z(a,b;c,d)$ zeros contains an $c\times d$ zero
submatrix.
\section{Proofs}
In this section we give the proofs of Theorems \ref{th:onea} and
\ref{th:two}.
\begin{lem}
\label{th:unicyclic}
%Let $G$ be a graph of order $2m$ which is either a tree or unicyclic
%graph. Then $G$ has an independent set of size $m$.
Let $G$ be a graph of order $n$. If $G$ is a tree, then $G$ has an
independent set of size $\lceil n/2\rceil$. If $G$ is a unicyclic
graph, then $G$ has an independent set of size $\lfloor n/2\rfloor$.
\end{lem}
\noindent
{\bf Proof.}
A tree of order $n$ is a bipartite graph and has either disjoint
independent sets of size $\lceil n/2\rceil$ and $\lfloor n/2 \rfloor$, or
an independent set of size $\lceil n/2 \rceil +1$. If $G$ is unicyclic,
then $G$ can be obtained from a tree of order $n$ by adding an edge and
hence $G$ contains an independent set of size $\lfloor n/2\rfloor$.
\hfill{$\Box$}
\begin{lem}
\label{th:transform}
Let $G$ be a graph of order $2t$ such that $G$ is not bisectable.
Assume that $G$ has a component $T$ which is a tree of odd order $k$ and a
component $B$ of order $l$
which is not a tree. Let $G'$ be the graph obtained from $G$
as follows:
\begin{enumerate}
\item[\rm (i)] If $B$ is a unicyclic graph of odd order, then replace
$T\cup B$ with $P_{k+l}$;
\item[\rm (ii)] Otherwise, remove any edge of $B$ which does not disconnect
$B$ and replace $T$ by a cycle of order $k$.
\end{enumerate}
Then $G'$ is not bisectable and $G'$ does not contain a larger independent
set than $G$.
\end{lem}
\noindent
{\bf Proof.} The nonbisectability of $G$ clearly implies the nonbisectability
of $G'$. First assume that $B$ is unicyclic of odd order.
By Lemma \ref{th:unicyclic}, $T$
has an independent set of size $(k+1)/2$ and $B$ has an independent
set of size $(l-1)/2$. Hence $T\cup B$ has an independent set of size
$(k+l)/2$. Since the maximum size of an independent set of
$P_{k+l}$ equals $(k+l)/2$, $G'$ does not contain a larger independent set
than $G$. Now assume that $B$ is not unicyclic of odd order. Removing an
edge of a graph increases the maximum size of an independent set by at most
1. Since $T$ has an independent set of size $(k+1)/2$ and the maximum size
of an independent set of a cycle of odd order $k$ equals $(k-1)/2$, $G'$
does not contain a larger independent set than $G$.\hfill{$\Box$}
\medskip
In the proof of Theorem \ref{th:onea} we shall make use of the following
result \cite{GT}.
\begin{lem}
\label{th:gt}
Let $a_1, a_2,\ldots,a_m$ be positive integers with $\sum_{i=1}^ma_i=b$.
If $m>\lfloor b/2\rfloor$, then for each positive integer $k$ with $k\leq b$
there exists a subset $I$ of $\{1,2,\ldots,m\}$ such that $k=\sum_{i\in I}
a_i$.
\end{lem}
\bigskip
{\bf Proof of Theorem \ref{th:onea} for $t$ odd.}
Let $G$ be a graph of order $2t$ with at most
$t+3$ edges. By applying Theorem \ref{th:turan} to $\overline{G}$, if $G$
does not contain an independent set of size $t$ then $G=2K_3\cup (t-3)K_2$
and hence $G$ is bisectable. The graphs for $t$ odd
given in the statement of the theorem have $t+4$ edges, do not contain an
independent set of size $t$ and are not bisectable. This proves the first
assertion of the theorem for $t$ odd.
We now assume that $G$ has exactly $t+4$ edges, and that $G$
does not contain an independent set of size $t$ and is not bisectable.
\medskip\noindent
Case 1: Each component of $G$ which is a tree equals $K_2$.
Then at least $t-4$ of the
components of $G$ are trees and thus are $K_2$'s.
Since $G$ has $t+4$ edges, at
least one component of $G$ is not a tree and hence $G$ has at least $t-3$
components. Since $G$ does not have an independent set of size $t$, $G$
has at most $t-1$ components.
\smallskip
\noindent
Case 1a: $G$ has exactly $t-3$ components. Thus $G=(t-4)K_2\cup F$
where $F$ is a unicyclic graph of order 8. By
Lemma \ref{th:unicyclic}, $F$ has an independent set of size $4$,
and thus $G$ has an independent set of size $t$, a contradiction.
\smallskip\noindent
Case 1b: $G$ has exactly $t-2$ components. Then either $t-4$ or $t-3$ of the
components of $G$ are trees. Suppose that $G$ has $t-4$ trees. Then $G$ has
exactly two components
$G_1$ and $G_2$ which are not trees (and so are unicyclic).
If $G_1$ and $G_2$ have even order (and so order equal to 4), then using Lemma
\ref{th:unicyclic}, we see that $G$ has an independent set of size $t$, a
contradiction. If $G_1$ and $G_2$ have odd order (and so of orders 3 and 5),
then $G$ is bisectable, another contradiction.
Now suppose that $G$ has $t-3$ trees. Then $G$ has exactly one component
$E$
which is not a tree, and this component
has order $6$ and has $7$ edges. Since $G$ does not
have an independent set of size $t$, $E$ does not have an
independent set of size 3. It is now easy to check that $E$ must be
the graph $H$ in the statement of the theorem. Thus $G=(t-3)K_2\cup H$.
\smallskip\noindent
Case 1c: $G$ has exactly $t-1$ components. Since $G$ does not have an
independent set of size $t$, each of its components is a complete graph.
It follows easily that $G=(t-2)K_2\cup K_4$.
\medskip\noindent
Case 2: There is a component $T$ of $G$ which
is a tree of order $2m$ with $m\geq 2$.
We replace $T$ in $G$ by $mK_2$ and obtain a graph $G'$ of order $2t$ with
at most $t+3$ edges. It follows from Lemma \ref{th:unicyclic} that the
maximum size of an independent set of $G'$ is at most $t-1$. By Theorem
\ref{th:turan}, $G'=2K_3\cup (t-3)K_2$ and hence $G=2K_3\cup P_4\cup
(t-5)K_2$. Since $G$ is not bisectable, $t=5$ and $G=2K_3\cup P_4$.
\medskip\noindent
Case 3: There is a component of $G$ which is a tree of odd order.
We repeatedly apply the transformation in Lemma \ref{th:transform} to obtain
a graph $G^{\dagger}$ none of whose components is a tree of odd order.
By Lemma \ref{th:transform}, $G^{\dagger}$ is a graph of order
$2t$ with $t+4$ edges which does not contain an
independent set of size $t$ and is not bisectable.
Applying what we have proved in Cases 1 and 2 to $G^{\dagger}$,
we conclude that
$G^{\dagger}$ equals $(t-2)K_2\cup K_4$, $(t-3)K_2\cup W$, or $2K_3\cup P_4$.
First suppose
that $G^{\dagger}$ was obtained from a graph $G^*$ by applying the
transformation (i) in Lemma \ref{th:transform}. Then one of the
components of $G^{\dagger}$ is a path of even length at least 4. Hence
$G^{\dagger}=2K_3\cup P_4$. This implies that $G^*=K_1\cup 3K_3$.
Since $G^*$ cannot be obtained by applying a transformation in Lemma
\ref{th:transform}, $G=K_1\cup 3K_3$.
Now suppose that $G^{\dagger}$ was obtained from a graph $G^*$ by applying the
transformation (ii) in Lemma \ref{th:transform}. Then one of the
components of $G^{\dagger}$ must be a cycle of odd length and again
$G^{\dagger}=2K_3\cup P_4$. This implies that
$G^*$, and hence $G$, has an independent set of size 5. Since $G$ has 10
vertices, this is a contradiction.\hfill{$\Box$}
\bigskip
{\bf Proof of Theorem \ref{th:onea} for $t$ even.}
Let $G$ be a graph of order $2t$ with at most
$3t/2$ edges. Suppose that $G$ does not contain an independent set of size
$t$ and $G$ is not bisectable. By arbitrarily adding new edges to $G$ we
obtain a graph $G^*$ with $3t/2 +1$ edges with the same properties.
Suppose $G^*$ is one of the graphs $(t/2 -1)K_2\cup H_a\cup H_b$ given in the
theorem. If we remove an edge of one of the $K_2$'s of
$G^*$, then we obtain an independent set of size $t$. Suppose that
we remove an edge
from, say, $H_b$. If the removal disconnects $H_b$,
we obtain a bisectable graph. Otherwise we obtain
an independent set of size $t$ by Lemma \ref{th:unicyclic}.
Therefore to complete the proof of the theorem it suffices to show that the
only graphs of order $2t$ with $3t/2+1$ edges which do not contain an
independent set of size $t$ and are not bisectable are the graphs
$(t/2-1)K_2\cup H_a\cup H_b$ given in the theorem.
We now assume that $G$ has exactly $3t/2+1$ edges, and that $G$
does not contain an independent set of size $t$ and is not bisectable.
Then $G$ has at least $t/2-1$ components which are trees.
Since $G$ does not have an
independent set of size $t$, Lemma \ref{th:unicyclic} implies that $G$ has
at least $t/2+1$ components.
First suppose that $G$ has at least $t/2$
components of even order. Let $2m_1,\ldots,2m_{t/2}$ be
the orders of $t/2$ components of $G$ with even order.
By the pigeonhole principle there is a
subset $I$ of $\{1,\ldots,t/2\}$ such that $\sum_{i\in I}m_i$ is a
multiple of $t/2$. Since
$\sum_{i=1}^{t/2}2m_i<2t$, it follows that $\sum_{i\in I} 2m_i=t$ and hence
$G$ is bisectable, a contradiction. Thus $G$ has at most $t/2-1$ components
of even order.
\medskip\noindent
Case 1: No component of $G$ is a tree of odd order.
Thus exactly $t/2 -1$ of the components of $G$ are trees and each has
even order, and all other components are unicyclic of
odd order. If there are at least
four components of odd order, then replacing the orders of two of these
components by their sum and arguing as above, we again contradict the
nonbisectability of $G$. Hence $G$ has exactly two components of odd order.
Let the order of the trees be $2m_1,\ldots, 2m_{t/2-1}$.
Suppose that at least one tree has order greater than 2 and hence
$\sum_{i=1}^{t/2-1}2m_i\geq t$. Since also
$\sum_{i=1}^{t/2-1}2m_i\leq 2t-6$, we have
\[\frac{t}{2}\leq \sum_{i=1}^{t/2-1}m_i\leq t-3.\]
It follows from Lemma \ref{th:gt} that there exists a subset $I$ of
$\{1,\ldots,t/2-1\}$ such that $\sum_{i\in I}m_i=t/2$. Once again we
contradict the nonbisectability of $G$.
We now conclude that $G=(t/2-1)K_2\cup H_a\cup H_b$ where $a$ and $b$ are odd
integers with $a+b=t+2$, $H_a$ is in ${\cal H}_a$ and $H_b$ is
in ${\cal H}_b$.
\medskip\noindent
Case 2: There is a component of $G$ which is a tree of odd order.
We repeatedly apply the transformation in Lemma \ref{th:transform} to obtain
a graph $G^{\dagger}$ none of whose components is a tree of odd order.
By Lemma \ref{th:transform}, $G^{\dagger}$ is a graph of order
$2t$ with $3t/2+1$ edges which does not contain an
independent set of size $t$ and is not bisectable.
Applying what we have proved in Case 1 to $G^{\dagger}$,
we conclude that
$G^{\dagger}$ is of the form $(t/2-1)K_2\cup H_a\cup H_b$ given in the
theorem. Since $G^{\dagger}$ does not contain a component which is a path
of even order at least 4, it was not obtained
by applying the
transformation (i) in Lemma \ref{th:transform}.
Thus $G^{\dagger}$ was obtained from a graph $G^*$ by applying the
transformation (ii) in Lemma \ref{th:transform}. Then one of $H_a$ and
$H_b$, say $H_a$, is a cycle of odd length.
Hence $G^*=T\cup H_b^*\cup (t/2-1)K_2$ where $T$ is a tree of order $a$ and
$H_b^*$ is obtained by adding a new edge to $H_b$. By Lemma
\ref{th:unicyclic}, $T$ has an independent set of size $(a+1)/2$, and
by an extension of the proof of Lemma \ref{th:unicyclic},
$H_b^*$ has an independent set of size $(b-1)/2$. Therefore
$G^*$, and hence $G$, has an independent set of size $t$,
a contradiction.\hfill{$\Box$}
\medskip
{\bf Proof of Theorem \ref{th:two}.} We first prove by induction on $r$
that a graph $G$ of order $rt$ whose number of edges
is at most
\[\min\{{r+1\choose 2}-1,rt-t\}\]
is $r$-partite with parts of size $t$. If $r=1$, then $G$ has no edges and
the conclusion holds. Now let $r>1$. By Theorem \ref{th:hs} we can assume
that $G$ has a vertex $v$ whose degree is at least $r$. Since $G$ has at
most $rt-t$ edges, the number of connected components of $G$ is at least $t$.
Thus there is an independent set $A$ of vertices such that $v\in A$ and
$|A|=t$. Let $G'$ be the graph obtained from $G$ by removing the vertices
in $A$. Since the degree of $v$ is at least $r$, $G'$ has at least
$r$ fewer edges
than $G$. Hence the number of edges of $G'$ is at most
\[{r+1\choose 2}-1 -r ={r\choose 2}-1.\]
If $r-1\leq 2t-2$, then
\[\min\{{r\choose 2}-1,(r-1)t-t\}={r\choose 2}-1\]
and hence by induction $G'$ is $(r-1)$-partite with parts of size $t$.
Assume that $r-1>2t-2$. Since $t\geq 2$, this implies that $r\geq t$ and
thus $G'$ has at least $t$ fewer edges than $G$.
Hence the number of edges of $G'$ is at most
\[ (rt-t)-t =(r-1)t -t= \min\{{r\choose 2}-1,(r-1)t-t\}.\]
Again by induction $G'$ is $(r-1)$-partite with parts of size $t$.
Since $A$ is an independent set of $t$ vertices of $G$, $G$ is $r$-partite
with parts of size $t$.
The graphs in (\ref{eq:cx1}) and (\ref{eq:cx2}) have order $rt$, are not
$r$-partite with parts of size $t$, and their number of edges is given by
(\ref{eq:two}), and hence the first assertion of the theorem follows.
We now prove that the graphs in (\ref{eq:cx1}) and (\ref{eq:cx2}) are the
only graphs with these properties.
Let $G$ be a graph of order $rt$ with number of edges given by
(\ref{eq:two}) which is not $r$-partite with parts of size $t$.
Since $G$ has at most $rt-t+1$ edges, $G$ has at least $t-1$ connected
components.
By Theorem \ref{th:hs}, $G$ has a vertex $v$ of degree at least $r$.
First suppose that $r<2t-2$. Then
\[{r+1\choose 2}2t-2$. Then $G$
has exactly $rt-t+1$ edges and at least $t-1$ of its components are trees.
Also $G$ cannot have an independent set of size $t$
containing $v$, since otherwise by the first assertion of the theorem, $G$
is $r$-partite with parts of size $t$.
Thus $G$ has exactly $t-1$ components, $v$ is adjacent to each vertex in
its component, and every other component is a complete graph.
Hence $G$ has the form (\ref{eq:cx2}).
Finally, suppose that $r=2t-2$. If $G$ has at least $t$ components,
then as in the case $r<2t-2$, $G$ is of the form (\ref{eq:cx1}). Thus we
may assume that $G$ has exactly $t-1$ components. Since $G$ has $rt-t+1$
edges, each of its components are trees.
$G$ cannot have an independent set of size $t$ which is incident
with at least $r+1$ edges, since otherwise
by the first assertion of the theorem, $G$
is $r$-partite with parts of size $t$.
This implies that
$v$ is adjacent to every vertex in its component, and every other
component is a complete graph.
Therefore $G$ has the form (\ref{eq:cx2}). \hfill{$\Box$}
\section{Characterization of ${\cal H}_n$}
In our characterization of the graphs in ${\cal H}_n$ we use the following
lemma which is a simple consequence of the well known theorem of
K\"{o}nig. Recall that a {\it perfect matching} of a graph is a set of
pairwise vertex disjoint edges which touch every vertex of the graph.
\begin{lem}
\label{th:char1}
Let $G$ be a bipartite graph of order $2t$. Then the maximum cardinality of an
independent set of $G$ equals $t$ if and only if $G$ has a perfect
matching.
\end{lem}
Let $H$ be a unicyclic graph of order $n$.
Then $H$ contains a unique cycle
$C=(x_1,x_2,\ldots,x_p,x_1)$. The connected components of the
subgraph of $H$ induced by the vertices
not belonging to $C$ are trees. These trees are
called the {\it trees of the unicyclic
graph} $H$. Each such tree is joined by an edge to exactly one vertex
$x_i$ of $C$.
%Those trees joined to $x_i$ are called
%the {\it trees joined to} $x_i$ ($(i=1,\ldots,p)$.
\begin{thm}
\label{th:char2}
Let $n\geq 3$ be an odd integer.
Then a unicyclic graph of order $n$ is in ${\cal
H}_n$ if and only if its unique cycle has odd length and each of its trees
is of even order and has a perfect matching.
\end{thm}
\noindent
{\bf Proof.} Let $G$ be a unicyclic graph of order $n$ and let the unique
cycle $C$ of $G$ have length $p$.
First assume that $p$ is odd and each of the trees of $G$
is of even order and has a perfect matching.
Each independent set of $G$ contains at most half of the vertices of
each of its trees by Lemma \ref{th:char1}
and at most $(p-1)/2$ vertices of $C$.
Thus the maximum cardinality of an independent set of $G$ is at most
$(n-1)/2$ and by Lemma \ref{th:unicyclic}, equals $(n-1)/2$.
Therefore $G$ is in ${\cal H}_n$.
Now assume that $G$ is in ${\cal H}_n$. Suppose to the contrary
that $p$ is even. Then $C$ has exactly two independent sets $A$ and $B$ of
size $p/2$. Since $n$ is odd, the number of trees of odd order of $G$ is
also odd. Without loss of generality assume that $A$ is joined to fewer
trees of odd order than $B$.
%We construct an independent set $I$ of $G$ with $A\subseteq I$
% of size greater than $(n-1)/2$ as follows.
Each tree of order $b$ joined to $B$ has by Lemma
\ref{th:unicyclic} an independent set of size $\lceil b/2\rceil$.
Each tree of order $a$ joined to $A$ has by (the proof of) Lemma
\ref{th:unicyclic} an independent set of size $\lfloor a/2\rfloor$ none of
whose vertices is joined to $A$. These independent sets along with $A$
give an independent set of $G$ of size greater than $(n-1)/2$,
contradicting the assumption that $G$ is in ${\cal H}_n$. Hence $p$ is
odd.
Now suppose to the contrary that at least one of the trees of $G$ has odd order.Let $q_i$ be the number of trees of odd order joined to vertex $x_i$ of
$C$ ($i=1,\ldots,p$), and let $q=q_1+\cdots+q_p$ be the number of odd trees
of $G$. Let $\cal I$ be the set
consisting of the $p$ independent sets of $C$ of size $(p-1)/2$. Each
vertex of $C$ is contained in exactly $(p-1)/2$ sets of $\cal I$.
The average number of trees of odd order joined to the sets in $\cal I$
equals
\begin{eqnarray*}
\frac{1}{p}\sum_{I\in {\cal I}} \sum_{x_i\in I} q_i
&=&
\frac{1}{p} \sum_{i=1}^p\;
\sum_{\{I\in {\cal I}: x_i\in I\}} q_i\\
&=& \frac{1}{p} \sum_{i=1}^p \frac{p-1}{2}\; q_i\\
&=& \frac{p-1}{p}\cdot \frac{q}{2}\\
&<& \frac{q}{2}.\\
\end{eqnarray*}
Hence there exists a set $A$ in $\cal I$ which is joined to fewer than
$q/2$ trees of odd order. As in the preceding paragraph we obtain an
independent set of $G$ of size greater than $(n-1)/2$,
contradicting the assumption that $G$ is in ${\cal H}_n$.
Thus all the trees of $G$ have even order.
If one of the trees of $G$ does not have a perfect matching, then using
Lemma \ref{th:char1} we again construct an independent set of size greater
than $(n-1)/2$. Hence each tree of $G$ has a perfect
matching.\hfill{$\Box$}
\medskip
Various characterizations of trees of even order are listed in \cite{Sim}.
\begin{thebibliography}{10}
\bibitem{Bo}
B.~Bollob\'{a}s,
\newblock {\it Extremal Graph Theory}, Academic, New York, 1978.
\bibitem{GT}
B.~Ganter and L.~Teirlinck,
\newblock A combinatorial lemma,
\newblock {\em Math. Zeitschrift}, 154 (1977), 153-156.
\bibitem{HS}
A.~Hajnal and E.~Szemer\'{e}di,
\newblock Proof of a conjecture of Erd\"{o}s,
\newblock in {\it Combinatorial Theory and its Applications Vol. II},
ed. by P.~Erd\"{o}s, A.~Renyi and V.~T.~S\'{o}s, Colloq. Math. Soc. J.
Bolyai 4, North-Holland, Amsterdam, 1970, 601-623.
\bibitem{Sim}
R.~Simion,
\newblock Trees with 1-factors and oriented trees,
\newblock {\it Discrete Mathematics}, 88 (1991), 93-104.
\bibitem{Si}
M.~Simonovits, A method for solving extremal problems in graph theory,
stability problems,
\newblock in {\it Theory of Graphs}, ed. by P.~Erd\"{o}s and G.~Katona,
Academic, New York, 1968, 279-319.
\end{thebibliography}
\end{document}