Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
College Discrete Math

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search