Show that a graph with 2n points and n2 + 1 edges necessarily contains a 3-cycle, but that we can find a graph with 2n points and n2 edges without a 3-cycle.
Solution
Induction. For n = 2, the result is obviously true, because there is only one graph with 4 points and 5 edges and it certainly contains a triangle. Suppose the result is true for n. Consider a graph G with 2n + 2 points and n2 + 2n + 2 edges. Take any two points P and Q joined by an edge. We now consider two cases. If there are less than 2n + 1 other edges to P and Q, then if we remove P and Q, we get a graph with 2n points and at least n2 + 1 edges, which must contain a triangle, so G does also. If there are at least 2n + 1 other edges then at least one point must be joined to both P and Q, but that gives a triangle.
Let G and H be disjoint sets each with n points. Join every point of G to every point of H by an edge. Then the resulting graph has n2 edges, but it does not contain any triangles, because two points of any triangle must belong to G or to H and in either case there is no edge connecting them.
© John Scholes
jscholes@kalva.demon.co.uk
4 Dec 1999