From: rjc@maths.ex.ac.uk (Robin Chapman)
Subject: Maximal number of edges in a graph
Date: 19 Feb 2001 13:48:17 -0500
Newsgroups: sci.math
Summary: Maximal number of edges in a triangle-free graph with  n  vertices?

Raul Peretz <raulper@netvis.com> wrote:

> What is the maximal number of edges that a triangle-free graph of n
> points can have? 

For n = 2m, m^2; for n = 2m+1, m(m+1). In both cases acheived
by the obvious bipartite graphs.

This is a specical case of Turan's therom. For proofs see texts
on graph theory (e.g. Bollobas's).

Robin Chapman, www.maths.ex.ac.uk/~rjc/rjc.html
==============================================================================

From: Dr Tim Robinson <mousemat@MailAndNews.com>
Subject: RE: Maximal number of edges in a graph
Date: Mon, 19 Feb 2001 22:32:40 -0500
Newsgroups: sci.math

>===== Original Message From raulper@netvis.com (Raul Peretz) =====
>What is the maximal number of edges that a triangle-free graph of n
>points can have?
>
>Thanks

A maximal triangle-free graph is probably bipartite.

For n=2m, there exists a triangle-free graph with m^2 edges.

For n=2m+1, there exists a triangle-free graph with m(m+1) edges.

------------------------------------------------------------
 When deja.com got taken over I switched to
                http://MailAndNews.com
==============================================================================

From: Fred Galvin <galvin@math.ukans.edu>
Subject: RE: Maximal number of edges in a graph
Date: Tue, 20 Feb 2001 00:52:36 -0600
Newsgroups: sci.math

On Mon, 19 Feb 2001, Dr Tim Robinson wrote:

> >===== Original Message From raulper@netvis.com (Raul Peretz) =====
> >What is the maximal number of edges that a triangle-free graph of n
> >points can have?
> 
> A maximal triangle-free graph is probably bipartite.

A 5-cycle is a "maximal" triangle-free graph, in the sense that you
can't add another edge to it and still have a triangle-free graph.
What you meant to say is that a triangle-free graph on n vertices,
which has the maximum possible number of edges, has to be bipartite.
The proof of that is really simple; I'll post it here for the benefit
of those who don't have a graph theory book handy.

Let G be a triangle-free graph on n vertices. Let A be an independent
set of vertices in G, where |A| = a is as large as possible. Let B be
the rest of the vertices; |B| = b = n-a. Now, each vertex in A has
degree at most b (since A is independent); and each vertex in B has
degree at most a (since the neighbors of a vertex are independent, and
since a is the maximum number of vertices in an independent set). It
follows (since the number of edges in a graph is half the sum of the
degrees) that the number of edges in G is less than or equal to the
number of edges in the complete bipartite graph K(a,b). In order for G
to have as many edges as K(a,b), each vertex in A would have to have
degree b; that is, each vertex in A would have to be joined by an edge
to each vertex in B; but then B would have to be an independent set
(since G is triangle-free), and so G itself would be bipartite. This
shows that the maximum number of edges, over triangle-free graphs on n
vertices, can only be attained by a complete bipartite graph. From
there, it's easy to see that the maximum number of edges for such a
graph is floor(n/2)*ceiling(n/2) = floor((n^2)/4).

-- 
People who don't have a sense of humor shouldn't try to be funny.