Weakly Pancyclic Graphs

A graph is called weakly pancyclic if it contains cycles of all lengths between its girth and circumference. A substantial result of Häggkvist, Faudree, and Schelp (1981) states that a Hamiltonian non-bipartite graph of order n and size at least ⌊(n−1)2/4⌋+2 contains cycles of every length l, 3⩽l⩽n. From this, Brandt (1997) deduced that every non-bipartite graph of the stated order and size is weakly pancyclic. He conjectured the much stronger assertion that it suffices to demand that the size be at least ⌈n2/4⌉−n+5. We almost prove this conjecture by establishing that every graph of order n and size at least ⌊n2/4⌋−n+59 is weakly pancyclic or bipartite.