Show that a finite graph in which every point has at least three edges contains an even cycle.
Solution
An even cycle is a set of distinct points P1, P2, ... , P2n such that there is an edge PiPi+1 for i = 1, 2, ... , 2n-1 and an edge P2nP1.
Let the number of points in the graph be n. We use induction on n. No graph with 3 or less points has at least three edges at every point. The only graph with 4 points and at least three edges at every point is the tetrahedron and that obviously has 4-cycles. So the result is true for n ≤ 4. Suppose it is true for less than n points.
Now take a graph G with n points. Starting at any point we move along a path until we come to a point already on the path. That gives us a cycle C. If C is even we are done. So assume it is odd.
If there is an edge between any two points of C, then we get an even cycle by going one way or the other around C (from the endpoints of the edge). Similarly, if any point not on C has an edge to more than one point on C, then we can get an even cycle by going one way or the other around C. So we can assume that every point not on C is joined to at most one point on C and that every point of C is joined to at least one point not on C. But now we can derive a new graph G' with less than n points by replacing C by a single point X. So we can find an even cycle in G'. If it does not involve X, then it is also an even cycle in G. If it does involve X, then we get an even cycle in G by going one way or the other around C.
Thanks to Vikram Nayak for fixing an error in the original solution
© John Scholes
jscholes@kalva.demon.co.uk
16 June 2002
Last corrected/updated 26 Jan 2004