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 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 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 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.