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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.