SERIE A — MATHEMATIK

A Sufficient Condition for all Short Cycles

Stephan Brandt*

Preprint No. A 95–24 August 1995

Abstract

Generalizing a result of Häggkvist, Faudree and Schelp, we prove that every nonbipartite graph of order n with more than (n − 1)^{2}/4 + 1 edges contains cycles of every length between 3 and the length of a longest cycle.

*FB Mathematik, Freie Universität Berlin, Graduiertenkolleg ‘Alg. Diskr. Mathematik’, Arnimallee 2–6, 14195 Berlin, Germany

e-mail: brandt@math.fu-berlin.de

Supported by Deutsche Forschungsgemeinschaft, Grant We 1265

In 1981, Häggkvist, Faudree and Schelp [6] proved the following sufficient condition for a hamiltonian graph to be pancyclic or bipartite.

Theorem 1 Every hamiltonian graph of order n with more than (n − 1)^{2}/4 + 1 edges is pancyclic or bipartite.

This generalizes a result of Bondy [1], who proved that every hamiltonian graph with at least n^{2}/4 edges is pancyclic or isomorphic to a complete balanced bipartite graph K_{n/2,n/2}. It is implicit in another paper of Bondy [2] that every graph (be it hamiltonian or not) with at least n^{2}/4 edges contains cycles of every length between 3 and the length of a longest cycle, unless the graph is K_{n/2,n/2}.

The object of this note is to prove the same generalization for the condition of Theorem 1. Let c(G) denote the length of a longest cycle of G.

Theorem 2 Every nonbipartite graph G of order n with more than (n − 1)^{2}/4 + 1 edges contains cycles of every length ℓ where 3 ≤ ℓ ≤ c(G).

It is not difficult to see, as we will prove in Lemma 3 below, that the hypothesis implies the triangle. In view of the complete balanced bipartite graph with one edge subdivided once, the bound can certainly not be reduced. Anyway, if we only require cycles of every length between the length of a shortest and a longest cycle in a nonbipartite graph, then there is hope for reducing the edge number constraint. Graphs containing cycles of every length between the length of a shortest and a longest cycle are called weakly pancyclic. Note that in many cases considerably weaker requirements ensure that a graph is weakly pancyclic than are needed to ensure that it is pancyclic (see [4]).

Conjecture 1 Every nonbipartite graph G of order n ≥ 3 with more than (n − 1)(n − 3)/4 + 4 edges is weakly pancyclic.

If true, the bound is best possible for every n ≥ 6. For n = 6 the 6-cycle with a 2-chord misses just C_{4}. For every r ≥ 3 the graphs consisting of K_{r−1,r} (K_{r−1,r+1}, resp.) and a 4-cycle C_{4}, where the endvertices of an edge of C_{4} are identified with two vertices in the larger part of the complete bipartite graph, have circumference 2r + 1 but no 2r-cycle. For even n ≥ 8 the graph consisting of K_{r,r} and K_{3} intersecting in one vertex, which misses all odd cycles of length more than three is another type of extremal graph.

As usual, V (G) and E(G) denote the vertex set and edge set of a graph G. For a vertex v, the subgraph induced by V (G) \ {v} is denoted by G − v, and for a fixed subgraph H of G, the graph G − H is the subgraph induced by V (G) \ V (H). Similarly, d_{H}(v) denotes the number of edges vx ∈ E(G) with x ∈ V (H). For a cycle C we always assume that C has an orientation, which is arbitrary but fixed, and for a vertex x of C the vertices x^{+i} and x^{−i} denote the i-th successor and predecessor, respectively, with respect to the orientation.

For the proof of Theorem 2 we need several tools. The first of them is an old result of Erdős and Gallai [5].

Theorem 3 Let G be a graph of order n. If every pair u, v of non-adjacent vertices satisfies d(u) + d(v) > n then every pair of vertices is joined by a hamiltonian path.

Lemma 1 Let G be a graph containing a cycle C of length k and let S be a subset of G − C with |S| ≥ 2, such that no vertex in S has a pair of consecutive neighbors on C. If

∑_{v∈S} d_{C}(v) > |S|k/(|S| + 1)

then there are two independent edges vx, wx^{+μ} where v, w ∈ S and x, x^{+μ} are vertices at distance μ with 1 ≤ μ ≤ |S| on the cycle.

Proof. It is easy to calculate that there must be a segment T of order |S| + 1 of the cycle such that there are |S| + 1 edges joining S and T. But then, using the fact that no vertex in S can be adjacent to all vertices in T, there must be two independent edges joining S and T which have the required properties. □

The following lemma can be seen as a generalization of Dirac’s famous Theorem [3], saying that every graph with minimum degree at least n/2 is hamiltonian.

Lemma 2 Let G be a non-hamiltonian graph of order n ≥ 3. Then for every longest cycle C there exists a vertex u in G − C with d_{G}(u) ≤ (n − 1)/2.

Proof. If G contains no cycles this is certainly true since 1 ≤ (n−1)/2. So let C be a longest cycle and let c be its length. By the maximality condition on C, no vertex in G − C can be adjacent to two consecutive vertices on C. Hence we obtain

d_{C}(v) ≤ c/2 for every vertex v in G − C.  (1)

By (1) we are done for c = n − 1, so we may assume that c ≤ n − 2. Moreover, assume that every vertex in G − C has degree at least n/2.

If there is a pair v, w of non-adjacent vertices in G − C with

d_{G−C}(v) + d_{G−C}(w) ≤ n − c,  (2)

then we must have equality in (1) for v and w and in (2). This implies that v and w have a common neighbor in G − C. Moreover, applying Lemma 1 to S = {v, w}, v has a neighbor x in C, such that w is adjacent to x^{+} or x^{+2}. So we obtain a cycle of length at least c + 2 through v and w, contradicting the maximality assumption on C.

Hence we may assume that d_{G−C}(v) + d_{G−C}(w) > n − c for every pair v, w of non-adjacent vertices in G − C. By Theorem 3 we obtain that G − C is hamilton-connected, and we derive that c ≥ n/2, since G − C is hamiltonian if n − c ≥ 3. Now every vertex in G − C must have a neighbor in C, which implies that c ≥ (n + 1)/2, using that G − C is hamilton-connected.

Applying Lemma 1 with S = V (G − C) we obtain that there must be a vertex u in G − C with d_{C}(u) ≤ c/(n − c + 1), since C is a longest cycle and G − C is hamilton-connected. Certainly, d_{G−C}(u) ≤ n − c − 1, so

d_{G}(u) ≤ n − c − 1 + c/(n − c + 1) ≤ n − 1 − (n − c)c/(n − c + 1) ≤ (n − 1)/2

as n − 1 ≥ c ≥ (n + 1)/2. □

Lemma 3 Every non-bipartite graph G of order n with more than (n − 1)^{2}/4 + 1 edges contains a triangle.

Proof. Let C be a shortest odd cycle of G and suppose c = |C| ≥ 5. By the minimality condition C must be an induced cycle and every vertex in G − C has at most two neighbors in C. Since G is triangle-free we conclude

|E(G)| ≤ c + 2(n − c) + (n − c)^{2}/4 ≤ (n − 1)^{2}/4 + 1. □

Lemma 4 Let G be a balanced bipartite graph of order n = 2r. If every pair of non-adjacent vertices u, v from different sides of the bipartition satisfy d(u) + d(v) > r then every pair x, y of vertices on different sides of the bipartition is joined by a hamiltonian path, unless {x, y} disconnects G.

Proof. We fix a hamiltonian cycle C of G which exists by a result of Moon and Moser [7]. If x and y are consecutive vertices on C then we are done. Otherwise, for an orientation of C, the vertices x and y are joined by an odd length path P = xx^{+} … y^{−}y and there is another odd length path P′ = y^{+}y^{+2} … x^{−2}x^{−}, such that P and P′ together span G. Moreover we can find a perfect matching M in G consisting of edges of P and P′. If y^{+} and x^{−} are not adjacent, then by the degree bound y^{+} and x^{−} must be adjacent to both ends of a matching edge e ∈ M. If e is in P then we obtain the desired hamiltonian path joining x and y, otherwise the subgraph induced by P′ is hamiltonian. Certainly, the same conclusion holds if y^{+} and x^{−} are adjacent.

Now we have a path P of odd length ≥ 3 and a hamiltonian cycle C in G − P. Since {x, y} is no cutset there must be an edge joining P − x − y to C. It is easy to observe, that G contains two disjoint odd length paths Q and Q′ spanning G which end in x and y, respectively. Let z and z′ be the other ends of Q and Q′. Again we can fix a perfect matching M′ of G consisting of edges of Q and Q′. If z and z′ are adjacent, then we are certainly done. Otherwise by the degree bound z and z′ are adjacent to both ends of a matching edge of M′, which implies the desired hamiltonian path between x and y. □

We are now prepared to prove the main result Theorem 2. Proof of Theorem 2. The proof is by induction on n. The statement is certainly true for n = 3 so suppose n ≥ 4. Take a longest cycle C in G. If |C| = n then we are done by Theorem 1. If |C| ≤ n−1 then by Lemma 2 there must be a vertex u of degree at most (n − 1)/2 in G − C. Since

⌊(n − 1)^{2}/4⌋ + 2 − (n − 1)/2 > (n − 2)^{2}/4 + 1,

by induction, G − u contains cycles of every length ℓ for 3 ≤ ℓ ≤ c(G − u) = c(G) unless G − u is bipartite.

Finally, assume G is not bipartite but G − u is bipartite. By Lemma 3 G contains a triangle. Obviously, every triangle of G must be spanned by u and an edge vw of G − u. Fix such an edge vw and let A ∪ B (|A| ≥ |B|) be a bipartition of G − u. Delete |A| − |B| vertices from A \ {v, w}. The resulting induced subgraph G′ of G − u is balanced bipartite of order 2|B| ≥ |C| and |E(G′)| > (|G′| − 1)/4 + 1, since G′ is obtained from G − u by consecutively deleting vertices of degree at most |B|. Since G′ is almost a complete balanced bipartite graph – at most |B| − 2 edges are missing – it is easily verified, that {v, w} cannot be a disconnecting set. Moreover, for any pair of non-adjacent vertices x ∈ A ∩ V (G′) and y ∈ B we obtain d_{G′}(x) + d_{G′}(y) ≥ |B| + 1, so v and w must be joined by a hamiltonian path in G′ by Lemma 4. Hence G contains a cycle of length n′ + 1, contradicting the maximality of C. □

References

[1] J. A. Bondy, Pancyclic graphs, J. Combin. Theory Ser. B 11 (1971), 80–84.

[2] J. A. Bondy, Large cycles in graphs, Discr. Math. 1 (1971), 121–132.

[3] G. A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. (3) 2 (1952), 69–81.

[4] S. Brandt, R. J. Faudree and W. Goddard, Weakly pancyclic graphs, in preparation.

[5] P. Erdős and T. Gallai, On maximal paths and circuits of a graph, Acta Math. Acad. Sci. Hungar. 10 (1959), 337–356.

[6] R. Häggkvist, R. J. Faudree and R. H. Schelp, Pancyclic graphs – connected Ramsey number, Ars Combin. 11 (1981), 37–49.

[7] J. W. Moon and L. Moser, On hamiltonian bipartite graphs, Israel J. Math. 1 (1963), 163–165.