Graph Theory

Date: 02/25/97 at 17:20:04
From: Konstantinos Koutsothodoros
Subject: Graph theory

I am not sure if you can help me with this question, but it's worth a 
try. This is a more difficult question from elementary graph theory:

Prove that the maximum number of edges in a graph of order n without 
an even cycle is [3/2(n-1)].

Try it out. I think you should start with a vertex x and then build 
the graph neighborhood by neighborhood. 

Thanks,
K.Koutsothodoros

Date: 02/25/97 at 19:01:27
From: Doctor Ceeks
Subject: Re: Graph theory

Hi,

My answer makes the following assumptions:

An even cycle is a closed path in the graph which does not intersect 
itself (i.e. each vertex in the path is traversed once as you travel 
around the cycle (except for the start and end vertex, which are the 
same).

No vertex can be connected to itself by an edge.  (Otherwise, with the 
above definition of even cycle, you could have 1 vertex and any number 
of edges, and there would be no even cycles.)

Sketch of proof:

First, show that [3(n-1)/2] is a sharp upper bound by actually 
exhibiting a graph for each n with n vertices and [3(n-1)/2] edges and 
no even cycles.  I'll omit this part.

Now, prove that if there are [3(n-1)/2]+1 or more edges, there must be
an even cycle by induction on n, the case n = 1 eliminated vacuously 
by the definitions, and the case n = 2 eliminated by an exhaustive 
check.

Suppose the result is true for n <= N and let G be a graph with N+1 
vertices (and more than [3N/2]+1 edges).

Note that if there exists a vertex in G attached to fewer than two 
edges, then one can consider the subgraph of G consisting of the other 
vertices and the edges between them.  This subgraph has 1 fewer 
vertice, and at least [3(n-1)/2]-1 edges. Since 
[3(n-1)/2]-1 = [3(n-1)/2 - 1] >= [3(n-2)/2], by induction, this 
subgraph has an even cycle, and hence G also has an even cycle.

Thus, every vertex has at least two edges coming from it (every vertex 
has degree at least 2).

This implies that G has a cycle decomposition.  That is, its vertices
can be decomposed into subsets such that the vertices in each subset
lie on a cycle.

If any of these cycles is even, we are done.

So assume all these cycles are odd (and hence, each subset consists of 
an odd number of vertices).  In fact, since no vertex is connected to 
itself, each of these subsets has at least 3 vertices, so the number 
of subsets in this cycle decomposition is at most (N+1)/3.

If in any of these subsets the associated cycle has an extra edge 
which passes from one vertex of the subset to another, we are done, 
because two cycles will be created, one of which must be even.  This 
allows us to assume that N > 4, since for N <= 4, (N+1)/3 < 2.  (That 
is, there will only be one cycle in the decomposition forcing the 
situation in this paragraph.)

So we can assume that the edges not involved in the cycle 
decomposition connect vertices of one cycle to vertices of another 
cycle.

Note that the cycle decomposition uses N+1 edges, and so there are at 
least [3N/2]-N edges not involved in the cycle decomposition. Also 
note that [3N/2]-N >= (N-1)/2 >= (N+1)/3, provided that N > 4. By the 
pigeon-hole principle, since there are at most (N+1)/3 subsets in the 
cycle decomposition, some two of them must be connected together by at 
least two edges.  (Picture two rings with two edges each connecting 
one vertex of one ring to a vertex of the other ring.)  Now you can 
use this bridge between rings to get your even cycle.  (There are 
three cases to consider: these two edges join the same vertices, these 
two edges have a common vertex, or these two edges share no vertex.)

-Doctor Ceeks,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/