\documentclass{elsart}
\usepackage{latexsym}
\def\({\left(}
\def\){\right)}  
\def\[{\left[}
\def\]{\right]}
\def\e{{\text{\rm e}}}
\let\epsilon=\varepsilon
\let\phi=\varphi
\def\deffont{\it}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%{\theoremheaderfont{\normalfont\slshape}
\newtheorem{property}{Property}%
%}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}
\begin{frontmatter}
  \title{The size of the largest bipartite subgraphs} 
  \author{Paul Erd\H os\thanksref{FAPESP}}
  \address{Mathematical Institute, Hungarian Academy of Sciences, P.O.B.~127,
  Budapest, H--1364 Hungary} 
  \thanks[FAPESP]{Part of this work was done while this author was visiting
  the University of S\~ao Paulo, supported by FAPESP (Proc.~94/2813--6).}  
  \author{Andr\'as Gy\'arf\'as\thanksref{OTKA}}
  \address{Computer and Automation Institute, Hungarian Academy of Sciences,
  Kende u.~13--17, Budapest, H--1111 Hungary} 
  \thanks[OTKA]{Supported by OTKA grant 7309.}
  \author{Yoshiharu Kohayakawa\thanksref{BRAZ}}
  \address{Instituto de Matem\'atica e Estat\'\i stica, Universidade de S\~ao
  Paulo, Cidade Universit\'aria, Rua do Mat\~ao~1010, 05508--900 S\~ao Paulo,
  SP, Brazil}
  \thanks[BRAZ]{Partially supported by FAPESP (Proc.~93/0603--1) and by CNPq
  (Proc.~300334/93--1 and ProTeM-CC-II Project ProComb).} 
\begin{abstract}
\vspace{-10pt}
\begin{center}
\sl
The last two authors dedicate this note to the memory of 
Professor Paul Erd\H os.
\end{center}
\bigskip\medskip
  \textbf{Abstract.}\enspace Simple proofs are given for results of
  Edwards concerning the size of the largest bipartite subgraphs of a
  graph. 
\end{abstract}
\end{frontmatter}

A widely applied remark of Paul Erd\H os~\cite{refErA} is that a graph
with~$e$ edges always contains a bipartite subgraph of at least~$e/2$
edges.  The importance of this remark justifies the search for
improvements.  Let~$f(e)$ be the largest integer such that any
multigraph with~$e$ edges must contain a bipartite subgraph with
$f(e)$ edges. Edwards~\cite{refEdA} proved that
\begin{equation}
  \label{eq:A}
  f(e)\geq\left\lceil{e\over2}+{1\over8}\left(\sqrt{8e+1}-1\right)
  \right\rceil.
\end{equation}
We shall refer to this lower bound for~$f(e)$ as {\it Edwards's formula\/}.
The purpose of this note is to give a simple proof of~(\ref{eq:A}) which seems
to be much more transparent and shorter than the original proof
in~\cite{refEdA}. Our approach also provides some other best possible lower
bounds for the size of the largest bipartite subgraphs in terms of the size
and order of the underlying graph (see Theorem~\ref{thm:A}).

It is easy to see that Edwards's formula gives~$f(e)$ exactly when
$e={m \choose 2}$ for some integer~$m$, and one may check that~$e=19$
is the first case in which~(\ref{eq:A}) is not tight:~$12=f(19)>11$, the
value given by Edwards's formula.  This raises the question whether the
difference between~$f(e)$ and the value given by Edwards's formula is
bounded.  This question was circulated through~\cite{refErB} and has
already been answered. Alon~\cite{refAlon} proved that if~$n$ is even
and~$e=n^2/2$, then
$$
$$ 
\begin{equation}
  \label{eq:B}
  f(e)-\left\lceil{e\over2}+{1\over8}\left(\sqrt{8e+1}-1\right)
  \right\rceil\geq ce^{1/4} 
\end{equation}
for some absolute constant~$c>0$. On the other hand, a construction 
given in~\cite{refAlon} shows that, for any positive integer~$e$, the
left-hand side of~(\ref{eq:B}) is bounded from above by~$Ce^{1/4}$ for
some constant~$C$.  A slight improvement of~(\ref{eq:A}) was proved by
Hofmeister and Lefmann (cf.~\cite{refHL}, Corollary~2.4). Alon~\cite{refAlon}
and Hofmeister and Lefmann~\cite{refHL} have independently found a short,
nonconstructive (in today's terminology, probabilistic) proof
of~(\ref{eq:A}). Our methods are constructive. 

We note that the asymptotics of~$f(e)$ can be determined not only for
graphs but for hypergraphs as well, even in a more general form.  This
was done by Erd\H os and Kleitman~\cite{refErK} with the probabilistic
method.  In this note, however, we restrict ourselves to graphs.

Assume that~$G$ is a multigraph with~$e$ edges. We shall use~$E(G)$
and~$V(G)$ to denote the set of edges and vertices of~$G$; their
respective cardinalities are called the {\it size\/} and the {\it
order\/} of the graph~$G$.  The subgraph induced by a subset~$S$ of
vertices of~$G$ is denoted by~$G[S]$. If~$G[S]$ is bipartite,
connected and has at least two vertices, we call it a {\it bipartite
block\/}. Since a bipartite block is an induced bipartite subgraph,
its partite classes are independent sets in~$G$.  We refer to these
classes as the {\it classes of the block\/}.  A partition~$P$
of~$V(G)$ into pairwise disjoint sets $I,S_1,S_2,\dots,S_t$ is called
a {\it partition of~$G$\/} if~$I$ is an independent set in~$G$ (called
the {\it independent block\/}) and each~$G[S_i]$ is a bipartite block.
The sum of the orders (respectively, sizes) of the~$G[S_i]$ ($1\leq
i\leq t$) are referred to as the {\it order\/} (respectively, {\it
size\/}) of~$P$.  Let us also define the {\it pseudosize\/} of the
partition~$P$ to be the total number of parallel classes of edges in
the bipartite blocks of~$P$. Thus the pseudosize of~$P$ is its `size'
when the multiplicity of the edges are disregarded.  The r\^ole of
partitions will be clear from the following simple lemma.

\begin{lem}\label{lem:LemmaA}
  If a graph~$G$ of size~$e$ admits a partition~$P$ of size~$s$,
  then~$G$ has a bipartite subgraph of at least~${1\over2}(e+s)$
  edges.
\end{lem}
\begin{pf}
  Starting from the bipartition~$(A,B)=(I,\emptyset)$, take the bipartite
  blocks of~$P$ in turn, in any order, and at each step add one of its classes
  to~$A$ and the other to~$B$, favouring the choice which brings as many edges
  as possible to~$(A,B)$.  \qed
\end{pf}

We shall apply the above lemma with suitable partitions.  As
customary, let~$\nu(G)$ denote the maximum number of pairwise disjoint
edges in~$G$.  In what follows, we only consider
{\it$\nu$-partitions\/} of~$G$, namely, partitions of~$G$ with
$t=\nu(G)$ bipartite blocks. Note that any maximum matching of~$G$
gives such a partition.  Moreover, observe that the bipartite blocks
of any~$\nu$-partition are induced stars (possibly having multiple
edges), since any two edges of any fixed block must meet. Among all
$\nu$-partitions of~$G$, consider the ones with largest possible
pseudosize. Amongst those, select one, say~$P_1$, with smallest
possible independent block~$I$.  Let~$s$ be the size of~$P_1$. The
following properties are immediate from the definition of~$P_1$.

\begin{property}\label{property:A}
  The order of~$P_1$ is at most~$2s$.
\end{property}

\begin{property}\label{property:B}
  Each bipartite block of~$P_1$ that has at least~$3$ vertices sends no edge
  into~$I$.
\end{property}

\begin{property}\label{property:C}
  If a bipartite block of~$P_1$ sends an edge into~$I$, then it sends exactly
  two, one from each of its two vertices. These two edges, which may have
  multiplicity larger than~$1$, are incident to the same vertex in~$I$, thus
  forming a triangle with the bipartite block.
\end{property}

The next observation is a little less obvious.   

\begin{lem}\label{lem:LemmaB}
  If~$G$ is connected, the partition~$P_1$ may be chosen so that its
  independent block~$I$ contains at most one vertex.
\end{lem}
\begin{pf}
  Suppose to the contrary that~$|I|\geq2$ for all possible choices
  for~$P_1$.  Among all these choices, let~$P_1$ be a
  partition of~$G$ with smallest possible {\it separation\/}
  within~$I$, that is, such that~$\min_{u,v}d(u,v)$ is smallest, where
  the minimum is taken over all pairs of distinct vertices~$u$,~$v\in
  I$ and~$d(u,v)$ denotes the distance between~$u$ and~$v$ in~$G$.
  Let this minimum be attained by the pair~$u_0$,~$v_0\in I$.
  Let~$u_0,x_1,x_2,\dots,v_0$ be a minimum length~$u_0$--$v_0$~path
  in~$G$, and, for each~$i=1,2,\dots$, let~$y_i$ be a neighbour
  of~$x_i$ within the bipartite block of~$x_i$.
  
  Property~\ref{property:C} immediately gives that~$d(u_0,v_0)\geq3$.
  Suppose~$d(u_0,v_0)=3$.  Again by Property~\ref{property:C}, we have
  that~$u_0y_1$ and~$y_2v_0$ are edges of~$G$. We now obtain a contradiction
  by observing that~$u_0,y_1,x_1,x_2,y_2,v_0$ is an augmenting path that
  contradicts the fact that~$P_1$ has~$\nu(G)$ bipartite blocks.
  
  Let us now assume that~$d(u_0,v_0)\geq4$. Replace the block~$\{x_1,y_1\}$ of
  the partition~$P_1$ by the block~$\{u_0,y_1\}$ to define a new
  partition~$P_1'$ of~$G$. Note that~$P_1'$ is a~$\nu$-partition, it has the
  same pseudosize as~$P_1$, and, furthermore, the independent blocks of~$P_1$
  and~$P_1'$ have the same cardinality. However,~$P_1'$ has separation no
  greater than~$d(x_1,v_0)<d(u_0,v_0)$, which contradicts the choice of~$P_1$.
  This contradiction shows that indeed~$|I|\leq1$, as required.  \qed
\end{pf}

Before we proceed, let us state the following consequence of the above
lemma, which may be of independent interest.

\begin{cor}\label{cor:Corollary}
  Any connected graph~$G$ contains a forest~$F$, all components of which are
  induced stars, with~$F$ covering all but possibly one vertex
  of~$G$.  \qed
\end{cor}

Properties~\ref{property:A}, \ref{property:B}, and~\ref{property:C} combined
with Lemmas~\ref{lem:LemmaA} 
and~\ref{lem:LemmaB} give lower bounds for the size of the largest bipartite
subgraphs of a graph in terms of its size and order. The bounds are sharp in
the sense that there are infinitely many graphs where these bounds are
attained. The second assertion in Theorem~\ref{thm:A} below is also due to
Edwards (see Theorem~6 in~\cite{refEdA}). Here we give a shorter, more
transparent proof.

\begin{thm}\label{thm:A}
  Let~$G$ be a graph of order~$n$ and size~$e$.  If~$G$ has no isolated
  vertices then it has a bipartite subgraph of size at least
  ${1\over2}\(e+{1\over3}n\)$. If~$G$ is connected, then it has a bipartite
  subgraph of size at least~${1\over2}\(e+{1\over2}(n-1)\)$.
\end{thm}
\begin{pf}
  Let us first assume that~$G$ has no isolated vertices.  In view of
  Lemma~\ref{lem:LemmaA}, to prove the first assertion in our theorem it
  suffices to prove that~$n\leq3s$.  Let~$E(P_1)$ denote the set of edges that
  belong to the bipartite blocks of~$P_1$. Thus~$s=|E(P_1)|$.  Define a
  function~$\phi\colon V(G)\to E(P_1)$ as follows.  If~$v$ is a vertex in a
  bipartite block, let~$\phi(v)$ be any edge of this bipartite block that is
  incident to~$v$. Now suppose~$v$ belongs to the independent block~$I$
  of~$P_1$. Since~$G$ has no isolated vertices, our vertex~$v$ and some
  bipartite block of~$P_1$ form a triangle
  (cf.~Property~\ref{property:C}).  Let~$\phi(v)$ be any edge in this 
  bipartite block. It is now easy to see that any edge in~$E(P_1)$ is the
  image of at most~$3$ vertices of~$G$.  Thus~$n\leq3|E(P_1)|=3s$, as
  required.
  
  Let us now assume that~$G$ is connected.  By Lemma~\ref{lem:LemmaB},
  we may assume that~$P_1$ has order at least~$n-1$. Combined with
  Property~\ref{property:A}, this gives that~$n-1\leq2s$. The second
  assertion of our theorem now follows from
  Lemma~\ref{lem:LemmaA}. \qed
\end{pf}

We now prove~(\ref{eq:A}). Amongst all~$\nu$-partitions of~$G$, let~$P_2$
have the maximal possible size. Then Properties~\ref{property:A},
\ref{property:B}, and~\ref{property:C} hold 
for~$P_2$. Moreover, because of the maximality of the size of~$P_2$,
the following extra property holds. 

\begin{property}\label{property:D}
  Let~$T$ be a triangle of~$G$ induced by a vertex in the independent block
  of~$P_2$ and a bipartite block of~$P_2$. The side of~$T$ determined by the
  bipartite block of~$P_2$ has multiplicity at least as large as the
  multiplicity of the other two sides.
\end{property}

Let~$H=G-I$ be the subgraph of~$G$ obtained from~$G$ by removing all
the vertices in the independent block~$I$ of~$P_2$, and let~$h$ be its
size.  By Property~\ref{property:A}, the graph~$H$ has order at
most~$2s$, where~$s$ is the size of~$P_2$. Therefore,
considering a factorization of~$K_{2s}$, one sees that there is a
partition~$P_3$ of~$G$ with size at least~$h/(2s-1)$, all of its
bipartite blocks are (possibly multiple) edges.  Property~\ref{property:D} implies
that~$h\geq e-2s$. Applying Lemma~\ref{lem:LemmaA} to the partitions~$P_2$
and~$P_3$, we obtain the following result.

\begin{prop}\label{prop:PropB}
  Assume that~$G$ is a graph of size~$e$.  Then~$G$ has a bipartite subgraph
  with at least  
$$
{e\over2}+{1\over2}\min\left\{
                         \max\left\{s,{e-2s\over2s-1}
                              \right\}\right\}
$$
  edges, where the minimum is taken over~$1\leq s\leq e$. \qed
\end{prop}

Edwards's lower bound~(\ref{eq:A}) follows from the above proposition on
solving the equation~$s=(e-2s)/(2s-1)$ for~$s$.

\bigskip
\noindent\textit{Acknowledgement}.\enspace  The authors are grateful to a
referee for pointing out a small imprecision in their original
manuscript.  

%\bibliographystyle{plain}
%\bibliography{refs}
\begin{thebibliography}{1}

\bibitem{refAlon}
N.~Alon.
\newblock Bipartite subgraphs.
\newblock {\em Combinatorica}.
\newblock To appear; manuscript of~1995.

\bibitem{refEdA}
C.S. Edwards.
\newblock Some extremal properties of bipartite subgraphs.
\newblock {\em Canadian Journal of Mathematics}, 25:475--485, 1973.

\bibitem{refErB}
P.~Erd{\H o}s.
\newblock Some recent problems in combinatorics and graph theory.
\newblock Manuscript (1995), and lecture at the {\it 26th Southeastern
  International Conference on Graph Theory, Combinatorics, and Computing\/},
  Boca Raton, 1995.

\bibitem{refErA}
P.~Erd{\H o}s.
\newblock On some extremal problems in graph theory.
\newblock {\em Israel Journal of Mathematics}, 3:113--116, 1965.

\bibitem{refErK}
P.~Erd{\H o}s and D.J. Kleitman.
\newblock On coloring graphs to maximize the proportion of multicolored
  {$k$}-edges.
\newblock {\em Journal of Combinatorial Theory}, 5:164--169, 1968.

\bibitem{refHL}
T.~Hofmeister and H.~Lefmann.
\newblock On {$k$}-partite subgraphs.
\newblock {\em Ars Combinatoria}.
\newblock To appear; manuscript of~1995.

\end{thebibliography}


\end{document}
