On the Turán Number for the Hexagon

Zoltan Füredi ^{∗}  Assaf Naor ^{†}  Jacques Verstraëte ^{‡}

December 29, 2003

Abstract

A long-standing conjecture in combinatorics, made by Erdős and Simonovits, is that the maximum number of edges in an n-vertex graph without a hexagon is asymptotically \frac{1}{2}n^{4/3} as n→∞. This conjecture corresponds to the asymptotic optimality of constructions of generalized quadrangles as a source of dense hexagon-free graphs. In this paper, we construct a counterexample to this conjecture. For infinitely many n, we construct an n-vertex hexagon-free graph of size

\frac{3(\sqrt{5}−2)}{(\sqrt{5}−1)^{4/3}} n^{4/3} + O(n) ≈ 0.534n^{4/3}.

On the positive side, we obtain the best known upper bound for the maximum number of edges in an n-vertex hexagon free graph: such a graph has size at most

λn^{4/3} + O(n^{7/6}) ≈ 0.627n^{4/3}

where λ is the real root of 16λ^{3} − 4λ^{2} + λ − 3 = 0. The same methods are applied to give an upper bound for the maximum number of edges in a hexagon-free m by n bipartite graph, and the bound is asymptotically tight when 2m = n or 2n = m.

1 Introduction

The forbidden subgraph problem, commonly known as a Turán-type problem, involves the determination of the maximum number of edges that an n-vertex graph may have if it contains no isomorphic copy of a fixed graph H. This number is called the Turán number for H, and denoted ex(n, H). Apart from its intrinsic interest, this type of problem has drawn considerable attention, since many graphs arising from natural algebraic constructions (for example, Cayley graphs and incidence graphs of projective geometries) are known not to contain certain subgraphs. The case of the complete graph K_{r} was studied by Turán in [33], where it was shown that:

∗Department of Mathematics University of Illinois at Urbana-Champaign 1409 W. Green Street Urbana, Illinois 61801-2975 E-mail: z-furedi@math.uiuc.edu

†Theory Group, Microsoft Research, One Microsoft Way, Redmond, WA 98052, United States. E-mail:

anaor@microsoft.com

‡Department of Combinatorics and Optimization, University of Waterloo, Math Faculty 200 University Avenue West, Waterloo, Ontario N2L 3G1, Canada. E-mail: jverstra@math.uwaterloo.ca.

ex(n, K_{r}) = ∑_{1≤i<j≤r−1} ⌊\frac{n + i − 1}{r − 1}⌋ · ⌊\frac{n + j − 1}{r − 1}⌋

Here, and in what follows, the notation a_{n} ∼ b_{n} is used as shorthand for the statement a_{n}/b_{n} → 1 as n tends to infinity. We also write V (G) and E(G) for the sets of vertices and edges of a graph G, and the size of G is the number of edges in G, denoted |G|.

For detailed surveys of Turán-type problems, we refer the reader to Füredi [18]. When the forbidden subgraph H is not bipartite, the Turán problem is well understood. The Erdős-Simonovits-Stone Theorem [13] asserts that as long as H is not bipartite,

ex(n, H) ∼ (1 − \frac{1}{χ − 1}) \binom{n}{2},

where χ is the chromatic number of H. Simonovits [30] further showed that if the chromatic number of H decreases under deletion of any edge of H, and n is sufficiently large, then ex(n, H) = ex(n, K_{χ}). In particular, for any odd cycle C, this shows ex(n, C) = ⌊n^{4}/4⌋ when n is large enough, and a complete bipartite graph with parts of sizes ⌊n/2⌋ and ⌈n/2⌉ is the unique extremal graph.

When the forbidden subgraph H is bipartite, much less is known. Kövari, Sós and Turán [21] showed that for the complete bipartite graph K_{r,s} with r ≤ s, ex(n, K_{r,s}) = O(n^{2−1/r}), which is known to be best possible for s > (r − 1)!, by the construction of norm graphs due to Kollár, Rónyai and Szabó [20]. It follows that for each bipartite graph H, there is a constant c > 0 such that ex(n, H) = O(n^{2−c}). Erdős [10] conjectured that for every bipartite graph H there are positive constants a, α such that ex(n, H) ∼ an^{1+α}. In particular, it a major open problem in combinatorics to determine the maximum size of a graph on n vertices containing no cycle of length 2k, or 2k-gon. Such a cycle is denoted by C_{2k}.

The Turán Problem for Even Cycles. The problem of determining the extremal number for 2k-gons is related to questions in projective geometry. Indeed, all the densest known constructions of dense graphs without short even cycles arise from certain rank two geometries, known as generalized polygons. These beautiful objects were first introduced and studied by Tits [32]. A d-regular generalized r-gon is a rank two geometry whose bipartite incidence graph is a d-regular graph of diameter r and girth 2r. Following Tits’ analysis, Feit and Higman [15] proved an important theorem stating that for each d ≥ 3, d-regular generalized r-gons exist only for r ∈ {3, 4, 6} (this theorem was, in part, motivated by the problem of the classification of finite simple groups). It is therefore of interest to evaluate ex(n, C_{2k}) for k ∈ \{2, 3, 5\}. Erdős and Simonovits [14] conjectured that ex(n, C_{2k}) ∼ \frac{1}{2}n^{1+1/k} for each k ≥ 2. As we shall see, this corresponds to the asymptotic optimality of generalized polygons as a source of constructions of graphs without 2k-gons.

For infinitely many values of q, Benson [3] gave constructions of (q + 1)-regular bipartite graphs with q^{k} + q^{k−1} + … + q + 1 vertices in each part, and cycles of length at most 2k when k ∈ {2, 3, 5}. A simple construction of graphs without cycles of length exactly 2k, for k ∈ {2, 3, 5}, without use of algebraic geometry, is found in Wenger [35]. The simplest case is the case k = 2. In this case, generalized triangles are precisely projective planes. The bipartite incidence graph of a projective plane is a bipartite graphs with q^{2} + q + 1 vertices in each part and \frac{1}{2}q(q + 1)^{2} edges. Furthermore, as shown in Alon and Spencer [2], every quadrilateral-free bipartite graph of maximum size must have this form. Using the existence of polarities for these projective planes, Erdős and Rényi [12] constructed a graph on q^{2} + q + 1 vertices with \frac{1}{2}q(q + 1)^{2} edges and no quadrilaterals. It was proved by Reiman [28] that ex(n, C_{4}) ≤ \frac{n}{4}(1 + \sqrt{4n − 3}) for all n, and Füredi [16] showed that for any prime power q > 13,

ex(q^{2} + q + 1, C_{4}) = \frac{1}{2}q(q + 1)^{2}.

According to Füredi [17], the unique quadrilateral-free graph on q^{2} + q + 1 vertices are polarity graphs of projective planes (Erdős-Renyi-type constructions), provided q is a prime larger than thirteen. Lazebnik, Ustimenko and Woldar [25] generalized the Erdős-Rényi construction, obtaining constructions, for k ∈ {3, 5}, of 2k-cycle-free graphs on q^{k} +…+q +1 vertices of size

\frac{1}{2}[(q + 1)(q^{k} + … + q + 1) − q^{⌊ \frac{k+1}{2} ⌋} − 1].

Thus Erdős and Simonovits conjectured (op. cit.) that these constructions are asymptotically optimal (they certainly are for k = 2). Their conjecture was disproved in [24] for k = 5, via a construction of a C_{10}-free graph with roughly \frac{4}{5^{6/5}} n^{6/5} edges.

The Turán Number for the Hexagon. The only remaining unsettled case of the Erdős-Simonovits conjecture in the range allowed by the Feit-Higman theorem is k = 3, i.e. the case of hexagons. In this paper, we refute the conjecture in this remaining case, and also obtain the best known bounds for ex(n, C_{6}):

Theorem 1.1 For infinitely many n, there are n-vertex hexagon free graphs of size at least

\frac{3(\sqrt{5}−2)}{(\sqrt{5}−1)^{4/3}} n^{4/3} + \frac{2(\sqrt{5}−2)}{(\sqrt{5}−1)}n − O(n^{2/3}) ≈ 0.534n^{4/3}.

On the other hand, any hexagon free graph has at most λn^{4/3}+O(n^{7/6}) edges, where λ ≈ 0.627 satisfies 16λ^{3} − 4λ^{2} + λ − 3 = 0.

The techniques used to prove this theorem may be appropriately modified to obtain an optimal upper bound for the maximum number of edges in an m by n hexagon-free bipartite graph, which improves upon the previous bounds established by Györi [19] and de Caen and Székely [9]. This maximum is denoted ex(m, n, C_{6}), and has its roots in a paper of Erdős, in which the analogous problem was analyzed for quadrilaterals, and applied to a problem in combinatorial number theory.

Theorem 1.2 For any pair of positive integers m and n,

ex(m, n, C_{6}) ≤ 2^{1/3}(mn)^{2/3} + O(m^{2/9}n^{8/9} + n^{2/9}m^{8/9} + m + n).

Furthermore, there are arbitrarily large integers n for which

ex(m, n, C_{6}) > 2^{1/3}(mn)^{2/3} + \frac{2}{9}(m + n) − O(n^{2/3} + m^{2/3})

when 2m = n or 2n = m.

Asymptotic Analysis. The densest known constructions of graphs without 2k-gons are due to Lazebnik, Ustimenko and Woldar [25] and Lubotsky, Phillips and Sarnak [23]. For all k, the constructions show that

ex(n, C_{2k}) ≥ n^{1+2/(3k)}.

The best known upper bounds for ex(n, C_{2k}), proved in [34], are

ex(n, C_{2k}) ≤ 8(k − 1)n^{1+1/k}.

The theoretical upper bound for graphs of girth at least 2k + 1 is a classical combinatorial result known as the Moore bound (see [4] page 180) in the case of regular graphs and, more recently, due to Alon, Hoory and Linial [1] in general. It follows from this bound that the maximum number ex(n, C_{3}, C_{4}, …, C_{2k}) of edges in an n-vertex graph of girth at least 2k +1 satisfies

ex(n, C_{3}, C_{4}, …, C_{2k}) ≤ \frac{1}{2}n^{1+1/k} + o(n^{1+1/k}).

It may be more natural to conjecture that there exist graphs of girth at least 2k +1 achieving this theoretical upper bound, as it is true for k ∈ {2, 3, 5}, however we lack constructions, especially for k = 4, of dense graphs without 2k-cycles. In fact, it is not even known in general whether the order of magnitude of ex(n, C_{2k}) is n^{1+1/k}.

For convenience, let f(n, k) = ex(n, C_{2k}) and g(n, k) = ex(n, C_{3}, C_{4}, …, C_{2k}). It is of particular interest to study the asymptotic behaviour, for each k, of f(n, k)/g(n, k) as n tends to infinity. An open problem of Erdős is to determine whether lim sup f(n, 2)/g(n, 2) > 1. Another way of stating this, in words, is whether graphs of girth five are always asymptotically sparser than the bipartite incidence graph of a projective plane of order n. One may ask the same question for k ≥ 3. In these cases, we are able to prove the following:

Theorem 1.3 Let k ≥ 3, and suppose that for some real number β > 0:

lim_{n→∞} \frac{g(n, k)}{n^{1+β}} exists.

Then

lim inf_{n→∞} \frac{f(n, k)}{g(n, k)} ≥ \frac{2k(\sqrt{k + 2} − 2)}{(k − 2)(\sqrt{k + 2} − 1)^{1+1/k}} → 2.

Prior to Theorem 1.3, it was unknown whether f(n, k)/g(n, k) might tend to one for some k ≥ 3. Bondy (personal communication) posed the following question: is it true that

\frac{f(n, k)}{g(n, k)} → ∞ as k → ∞.

In fact, for k ∉ {2, 3, 5}, it is not known whether the limit superior of the above ratio is finite. We therefore make the following conjecture, which gives evidence for this finiteness:

Conjecture Let k ≥ 3, and let G be a 2k-cycle-free graph. Then some positive proportion of the edges of G span a graph containing no cycles of length at most k + 1.

It may even be true that we can replace k + 1 with 2k + 1 in this conjecture. Partial evidence for the conjecture was given by Kühn and Osthus [22], who showed that the above conjecture is true when k + 1 replaced by a logarithmic function of k. In Section 3, we will prove that the conjecture is true when k = 3 i.e. in the case of hexagon-free graphs.

Theorem 1.4 Let G = (V, E) be a hexagon-free graph. Then there is a subgraph of G of girth five, containing at least \frac{1}{2}|E| edges. Equality holds if and only if G is a graph consisting of an edge-disjoint union of complete graphs of order four or five.

This generalizes results of Györi [19] and Kühn and Osthus [22], and furthermore gives the unique family of graphs for which there is no subgraph of girth five with more than \frac{1}{2}|E| edges. It would be interesting to see how many edges must be deleted from a hexagon-free graph to obtain a graph of girth at least seven or eight.

Pseudorandomness. Let us say that an n-vertex graph with p\binom{n}{2} edges is pseudorandom if the second largest eigenvalue λ of its adjacency matrix is o(pn). A natural question is whether the extremal graphs for a 2k-cycle are pseudorandom. It is fairly straightforward to prove that the graphs constructed by Lazebnik, Ustimenko and Woldar [25] are indeed pseudorandom. In particular, for the hexagon-free graph on n = q^{3} + q^{2} + q + 1 vertices with \frac{1}{2}[(q + 1)(q^{3} + q^{2} + q + 1) − q^{2} − 1] edges, λ = o(q) = o(n^{1/3}). This follows essentially from the fact that the number of paths of length three in in this graph is (1 − o(1))\binom{n}{2} (see Chung and Graham [8] for details). Our construction in Section 2 will start with such a graph, but eventually we produce a family of denser graphs which are not pseudorandom. In fact, we will produce a large number of non-isomorphic denser graphs, each with roughly the same number of edges. The constructions as well as our upper bounds for ex(n, C_{6}) indicate that it may be difficult to determine lim_{n→∞} ex(n, C_{6})n^{−4/3}, if the limit exists.

2 Constructions

Our construction of dense hexagon-free graphs starts with a known construction and modifies it. Although the modifications may appear somewhat mysterious at first sight, the reader will discover from the proof of our upper bound for ex(n, C_{6}) that these modifications cannot be avoided. We attempt to present a self-contained description of our construction, and therefore begin by outlining the construction of the known (base) graph.

In what follows, the number of edges in a graph G is denoted by |G|, and uv ∈ G means that the pair {u, v} is an edge of G.

2.1 Generalized Quadrangles and Polarities

We start with a purely combinatorial description of the base graph, and then give a brief motivation for this construction from projective geometry. The base graph is a graph G on 𝔽_{q}^{3}, where q = 2^{2t+1} and t is any positive integer. Two distinct vertices (a, b, c) ∈ 𝔽_{q}^{3} and (d, e, f) ∈ 𝔽_{q}^{3} are adjacent in G if

\{ \begin{matrix}ad^{2^{t}} & = f^{2^{t}} − b \\ ae & = e^{2^{t+1}} − (df)^{2^{t}} − c. \end{matrix}

It is shown in [25] that this graph has \frac{1}{2}q^{4} − \frac{1}{2}q^{2} edges and no cycles of length six. This may be checked technically, however, it is more instructive to turn to the geometric background of this construction. For this, the notion of a polarity is required.

The base graph G which we defined above is defined from an automorphism of a certain bipartite graph, known as a generalized quadrangle. This automorphism is known as a polarity. For an n by n bipartite graph H, with parts L and R, a polarity π on H is an involutary automorphism of H: π^{2} = Id, π(L) = R, π(R) = L, and uv ∈ H if and only if π(v)π(u) ∈ H. A polarity π of a rank two geometry (i.e. a set of points and lines and an incidence relation on them) is precisely a polarity of the incidence graph of the geometry, and one requires that π sends points to lines, lines to points and incidence is preserved. The polarity graph of H with respect to π is the graph H_{π} defined on L by H_{π} = {uv : uπ(v) ∈ H}. Let n_{π} denote the number of fixed points of π. The base graph G is precisely the polarity graph of some bipartite graph H. We will make this explicit in the next subsection, where we describe H and use it to deduce certain useful facts about G = H_{π}. To do this, we require some basic facts on polarity graphs in general: these propeties are straightforward to verify (see [25]). For any polarity π of a bipartite graph H:

(1) H_{π} has |R| vertices and |H_{π}| = \frac{1}{2}|H| − n_{π}.
(2) If H_{π} contains a (2k + 1)-gon, then H contains a (4k + 2)-gon.
(3) If H_{π} contains a 2k-gon, then H contains a 2k-gon.

In what follows, we refer to the base graph as the polarity graph of a generalized quadrangle or, simply, the polarity graph.

2.2 Properties of the Polarity Graph

The bipartite graph H of which G is the polarity graph is the bipartite incidence graph of a rank two geometry, known as the affine part of a generalized quadrangle. The graph H has parts L = R = 𝔽_{q}^{3}, in which the vertex (a, b, c) ∈ L is joined to (d, e, f) ∈ R if ad = e − b and ae = f − c. The simplest analysis showing that this graph has no cycles of length four or six is presented in Wenger [35], where only elementary linear algebra is used. It is also easily verified that H has q^{4} edges and q^{3} vertices in each part. The polarity π on H which gives G = H_{π}, used in [25], is defined by

\begin{matrix}π(a, b, c) = (a^{2^{t+1}}, (ab)^{2^{t}} + c^{2^{t}}, b^{2^{t+1}}) & for (a, b, c) ∈ L \\ π(d, e, f) = (d^{2^{t+1}}, f^{2^{t}}, e^{2^{t+1}} + (df)^{2^{t+1}}) & for (d, e, f) ∈ R. \end{matrix}

The fact that π is a polarity on H was proved in Peykre [27]. As H has girth eight, (1) and (3) imply that G = H_{π} has \frac{1}{2}q^{4} − \frac{1}{2}q^{2} edges. By (2) and (3), G has no triangles, quadrilaterals or hexagons.

2.3 Construction of Dense Hexagon-Free Graphs

We begin with a construction showing that Theorem 1.2 is optimal. To do so, let H be the incidence graph of a generalized quadrangle, with parts L and R, as defined above. Then H has girth eight. Now add a new set of vertices L′ to H, and let ϕ : L′ ↔ L be a bijection. Define a bipartite graph H′ with parts R and L ∪ L′ as follows:

H′ = {uv : u ∈ L ∪ L′, v ∈ R, uv ∈ H or ϕ(u)v ∈ H}.

This is a q^{3} by 2q^{3} bipartite graph with 2q^{4} = 2^{1/3}(2q · q)^{2/3} edges. To see that H′ contains no hexagons, suppose for a contradiction that C = (v_{1}, v′_{2}, v_{3}, v′_{4}, v_{5}, v′_{6}, v_{1}) is a hexagon in H′. By symmetry, we may assume C contains at least four edges of H. Form the closed walk (v_{1}, v_{2}, v_{3}, v_{4}, v_{5}, v_{6}, v_{1}) in H where v_{i} = v′_{i} if v′_{i} ∈ L and v_{i} = ϕ(v′_{i}) if v′_{i} ∈ L′. Since H contains no cycles of length at most six, this closed walk of length six must traverse each edge of a tree in H twice. Note that each edge of the cycle corresponds to a step in the walk. However, the tree has at least four edges, since C contains at least four edges of H. This implies the walk has length at least eight, a contradiction. Therefore H′ contains no hexagons. A slightly better construction is provided if we begin with a generalized quadrangle with q^{3} + q^{2} + q + 1 points and in which each line contains q + 1 points. In this case, the construction above gives a bipartite graph with 2(q + 1)(q^{3} + q^{2} + q + 1) edges, and if n = 2(q^{3} + q^{2} + q + 1) and m = q^{3} + q^{2} + q + 1, this is asymptotic to

2^{1/3}(mn)^{2/3} + \frac{2}{9}(m + n) + O(m^{2/3} + n^{2/3}).

We now give a construction for the lower bound in Theorem 1.1. Start with the base graph G = H_{π} on the vertex set V, which has size n = q^{3}. Let (A, B) be a partition of V into two sets A and B, let G[A] be the subgraph of G induced by A, and suppose that each edge in G[A] is given an orientation. Write u → v if the edge uv ∈ G[A] is oriented from u to v. We create from the pair (G, A) a new graph G^{A}. Let W be a set of vertices disjoint from V with |W | = |A|, let ϕ be a bijection W ↔ A and let G^{A} be the graph on V ∪ W defined as follows:

|G^{A}| = {uv : u, v ∈ V, uv ∈ G} ∪ {uv : uϕ(v) ∈ G, u ∈ B, v ∈ W }
∪ {uv : u ∈ A, v ∈ W, ϕ(v) → u}.

We claim that G^{A} contains no hexagons. To see this, suppose for a contradiction that C = (v_{1}, v_{2}, v_{3}, v_{4}, v_{5}, v_{6}, v_{1}) is a hexagon in G^{A}. Form the closed walk (u_{1}, u_{2}, u_{3}, u_{4}, u_{5}, u_{6}, u_{1}) in G where u_{i} = v_{i} if v_{i} ∈ V and u_{i} = ϕ(v_{i}) if v_{i} ∈ W. This closed walk must occur on a tree T ⊂ G, since G has no cycles of length three, four or six. Therefore T has at most three edges. On the other hand, if C contains at most one vertex of W, then there are at least four edges of C in G, so T has at least four edges, a contradiction. Therefore C contains at least two vertices of W. However, we claim that this also implies T has at least four edges. In this case, note that there are two vertices u, v ∈ W of C, each incident with two edges of G^{A}, since no vertices of W are adjacent. The four edges of C incident with u and v correspond to two subpaths of T of length two whose center vertices are ϕ(u) and ϕ(v), by construction. If these subpaths share an edge, then the edge is ϕ(u)ϕ(v). However, then u is adjacent to ϕ(v) and v is adjacent to ϕ(u), which contradicts the fact that u and v are only adjacent to out-neighbours of ϕ(u) and ϕ(v), respectively. Therefore the two subpaths do not share an edge, and T has at least four edges. This contradiction shows that G^{A} has no hexagons.

We now choose A so as to maximize the number of edges in G^{A}. Fix a positive integer K < n and let A ⊂ V be a subset of size K, chosen uniformly at random among all such subsets. Observe that in expectation, the number of edges incident with A is at least \frac{K}{n} (2 − \frac{K−1}{n−1}) |G|. Therefore we can choose such an A for which the number of edges in G^{A} is at least

|G| + \frac{K}{n} (2 − \frac{K−1}{n−1}) |G|.

The number of vertices in G^{A} is N = n + K. Choosing K = ⌊(\sqrt{5} − 2)n⌋ it follows that

|G^{A}| ≥ \frac{3(\sqrt{5}−2)}{(\sqrt{5}−1)^{4/3}} N^{4/3} − O(N^{1/3}).

This construction almost gives the expression claimed in Theorem 1.1. To obtain a slightly better construction, and the expression in Theorem 1.1, one begins with H as the bipartite incidence graph of a generalized quadrangle with q^{3} + q^{2} + q + 1 points, in which each line contains q + 1 points. In this way, the polarity graph G = H_{π} (which is described in [25]) has q^{3} + q^{2} + q + 1 vertices and size

\frac{1}{2}[(q + 1)(q^{3} + q^{2} + q + 1) − q^{2} − 1] = \frac{1}{2}q(q^{3} + 2q^{2} + q + 2).

Writing n = q^{3} + q^{2} + q + 1, the number of edges in G is \frac{1}{2}n^{4/3} + \frac{1}{3}n − O(n^{2/3}), so our construction G^{A} applied to the denser graph G has size at least

\frac{3(\sqrt{5}−2)}{(\sqrt{5}−1)^{4/3}} N^{4/3} + \frac{2(\sqrt{5}−2)}{(\sqrt{5}−1)}N − O(N^{2/3}).

This completes the construction for the lower bound in Theorem 1.

Finally, we remark that the constructions give a family of graphs with roughly the same number of edges. Indeed, the base graph G is pseudorandom, and it is known that in such graphs, the number of edges between between disjoint sets A and B in G and induced by A in G is roughly the same as in a random graph with the same density. Therefore we may choose any subset A of the appropriate size and any orientation of the edges within A, and the construction will have asymptotically the same density. Now the orientation of edges in A produces the non-isomorphism: in fact the outdegree sequence of the vertices in A is exactly the degree sequence of the K new vertices added to produce G^{A}.

2.4 Constructions for Longer Even Cycles

Here we give a generalization of the construction for hexagons to graphs without cycles of length 2k, starting with a fixed graph of girth at least 2k. This constitutes the proof of Theorem 1.3. We proceed similarly to the construction for hexagons. Fix k ≥ 2, and let G be an extremal graph containing no cycles of length at most 2k. Let A be a subset of the vertex set V of G of size K as before, i.e. the number of edges incident with A is at least

\frac{K}{n} (2 − \frac{K − 1}{n − 1}) |G|.

Take an arbitrary orientation of the edges inside A. Let ℓ be a positive integer less than k −1. Define a new graph G_{ℓ}^{A} by taking disjoint sets {A_{v} : v ∈ A} of size ℓ and

G_{ℓ}^{A} = G ∪ ⋃_{v∈A}{xy : x ∈ A_{v}, y ∈ V \ A, vy ∈ G} ∪ {xy : x ∈ A_{v}, y ∈ V \ A, v → y}.

We prove that G_{ℓ}^{A} contains no cycles of lengths 2ℓ + 3, 2ℓ + 4, …, 2k. First, let us show that the vertex set of every cycle in G_{ℓ}^{A} of length m ≤ 2k is contained in A_{v} ∪ V for some v ∈ A. We proceed by induction on m. For m = 4, if a quadrilateral in G_{ℓ}^{A} contains a vertex of A_{v} and a vertex of A_{w}, then v and w have a pair of common neighbours in G, which implies v = w since G does not contain a quadrilateral. Now suppose that we have proved the statement for cycles of length less than m, and suppose G_{ℓ}^{A} contains a cycle C of length m, where m > 4. If C contains two vertices of some A_{v}, then these vertices have the same neighbourhood in G_{ℓ}^{A}, so we find a cycle C′ of length strictly less than m in G_{ℓ}^{A}. By induction, all vertices of C′ not in G are contained in A_{v}, which implies the same for C, as required. We may therefore assume |V (C) ∩ A_{v}| ≤ 1 for all v ∈ A. Now C corresponds to a closed walk of length m on a tree T with at most ⌊m/2⌋ edges in G. Let x be the number of vertices of C not in G. Then T has at least 2x + 1 vertices. Hence 2x + 1 ≤ ⌊m/2⌋ + 1. On the other hand, T has at least m − x vertices, implying m − x ≤ ⌊m/2⌋ + 1. It follows that m = 4, which we have dealt with above. This completes the induction. Now we show that G_{ℓ}^{A} contains no cycles of length at least 2ℓ+4 and at most 2k. Suppose C is such a cycle. By what we have proved, V (C) ⊂ A_{v} ∪ V for some v ∈ A. Now some subpath of C disjoint from v joins two neighbours of vertices in A_{v}, since C contains at most 2ℓ edges incident with A_{v}, and therefore at least three edges of G, not all incident with v. This gives a cycle in G, of length at most |C|, a contradiction. Therefore G_{ℓ}^{A} contains no cycles of length at least 2ℓ + 3 and at most 2k.

We consider the graph G^{A} = G_{k−2}^{A} for our construction. Suppose that for some β, γ > 0,

lim_{n→∞} \frac{g(n, k)}{n^{1+β}} = γ.

Recall that g(n, k) is the maximum number of edges in an n-vertex graph of girth at least 2k + 1. For convenience, let N = n + (k − 2)K, the number of vertices in G^{A}. Then, denoting α = K/n, the number of edges in G^{A} satisfies:

lim_{n→∞} \frac{|G^{A}|}{g(n, k)} = c_{k}(α) = \frac{(k − 2)α^{2} + 2(k − 2)α(1 − α) + 1}{(1 + α)^{1+β}}.

We note that β ≤ \frac{1}{k}, by the Moore bound [1]. Therefore

c_{k}(α) ≥ \frac{(k − 2)α^{2} + 2(k − 2)α(1 − α) + 1}{(1 + α)^{1+1/k}}.

Maximizing over all choices of α ∈ (0, 1), we find c_{k}(α) achieves a maximum at α = \frac{\sqrt{k+2}−2}{k−2} in which case, for k ≥ 3,

c_{k} = max_{α∈(0,1)} c_{k}(α) = \frac{2k(\sqrt{k + 2} − 2)}{(k − 2)(\sqrt{k + 2} − 1)^{1+1/k}} .

Then c_{3} ≈ 1.068, c_{4} ≈ 1.130, c_{5} ≈ 1.184. Also,

c_{k} ∼ 2 − \frac{2}{\sqrt{k}} − O(\frac{log k}{k} )

as k tends to infinity. In particular, by starting with the the polarity graph of a generalized hexagon, this gives a denser construction of a graph without cycles of length ten than that presented in [25], namely

ex(n, C_{10}) ≥ \frac{10(\sqrt{7}−2)}{3(\sqrt{7}−1)}N^{6/5} + \frac{2}{5}N − O(N^{4/5}) ≈ 0.592N^{6/5}.

3 The Structure of Hexagon-Free Graphs

A priori, it may seem plausible that an extremal hexagon-free graph on n vertices “resembles” a regular graph of girth seven. However this is not at all the case. The constructions of the last section are not regular, and have a very large number of triangles, quadrilaterals and pentagons. We will see in the next few sections that an extremal hexagon-free graph must indeed contain many quadrilaterals. In the present section, we analyse how quadrilaterals may appear in a hexagon-free graph.

3.1 Block Subgraphs

Let G be a hexagon-free graph. A complete bipartite graph K ⊂ G is called maximal if it contains a cycle and is not properly contained in any other complete bipartite graph in G. If K has at least six edges, then K consists of a unique pair of vertices of degree at least three, denoted base(K), together with the set of all their common neighbours. An intersecting family of maximal complete bipartite subgraphs is a non-empty family K of maximal complete bipartite subgraphs such that

E(K) ∩ E(K′) ≠ ∅ for all K, K′ ∈ K.

An intersecting family K is a maximal intersecting family if K ∪ {K} is not an intersecting family for all maximal complete bipartite subgraphs K ⊂ G with K ∉ K. A block subgraph of a hexagon-free graph is any subgraph comprising the union of a maximal intersecting family. The main structural result of this section is as follows:

Theorem 3.1 Let F be the subgraph of a hexagon-free graph G consisting of all edges of G which are not in any quadrilateral. Then G = F ∪H_{1}∪H_{2}∪…∪H_{r} where H_{i} are edge-disjoint block subgraphs of G which are edge-disjoint from F.

This theorem will be used heavily throughout the rest of the paper. In order to prove the theorem, we will show that block subgraphs fall into four different classes of subgraphs. We now describe these types of subgraphs.

Let us say that a maximal complete bipartite subgraph is isolated if it does not share an edge with any other maximal complete bipartite subgraph. A subgraph has type (1) if it is an isolated maximal complete bipartite subgraph. A subgraph is of type (2) if its vertex set is of the form {u, v, w} ∪ A ∪ B where {u, v, w} induces a triangle, A is the set of all common neighbours of {u, v} excluding w, B is the set of all common neighbours of {u, w} excluding v, A and B are non-empty, and A ∩ B = ∅. A subgraph is of type (3) if its vertex set is of the form A ∪ {u, v, w, x} where {u, v, w, x} induces a complete graph on four vertices, and A is the set of all common neighbours of {u, v}, excluding w and x. Finally, a subgraph is of type (4) if it has five vertices and minimum degree at least three. Examples of these types of subgraphs are illustrated below:

Type (4) Type (2)

Type (3)

The following theorem is the next main structural result of this section: it is a classification of the block subgraphs of a hexagon-free graph. Its proof involves a somewhat technical case analysis, which is deferred to Appendix 8. Let us say that a subgraph H of a given graph G is strongly induced if any path of length at most four in G with endpoints in H is entirely contained in H.

Theorem 3.2 Let H be a block subgraph of a hexagon-free graph. Then H has type (1), or H is a strongly induced subgraph of type (2), (3) or (4).

Assuming the validity of Theorem 3.2, it is a short step to deduce Theorem 3.1:

Proof of Theorem 3.1 Let H_{1}, H_{2}, …, H_{r} be the block subgraphs of G. Then F is edgedisjoint from H_{1} ∪ H_{2} ∪ … ∪ H_{r}, since every edge of H_{1} ∪ H_{2} … ∪ H_{r} is in at least one quadrilateral in G, and no edge of F is in a quadrilateral in G. Furthermore,

E(G)\E(F) ⊂ E(H_{1}) ∪ E(H_{2}) ∪ … ∪ E(H_{r}),

since an edge in a quadrilateral is contained in some maximal complete bipartite subgraph of G, which is contained in some block subgraph of G, by definition of block subgraphs. It remains to show that the block subgraphs H_{1}, H_{2}, …, H_{r} are edge-disjoint. By Theorem 3.2, there are four types of block subgraphs. A block subgraph of type (1) is clearly edge-disjoint from all other block subgraphs, by definition. We now require the following two facts:

Fact 1. Let H and H′ be block subgraphs of types (2), (3) or (4), and suppose that H and H′ have the same vertex set. Then H = H′.

Fact 2. Let u, v, w be three vertices in a block subgraph H of type (2), (3) or (4). Then there is a path of length at most four containing w and with endpoints u and v.

These facts follow from Theorem 3.2. Now suppose H and H′ are block subgraphs of type (2), (3) or (4), sharing an edge {u, v}. It is sufficient to prove H = H′. If not, then Fact 1 shows that V (H) ≠ V (H′). Let w ∈ V (H′)\V (H). By Fact 2, there is a path P ⊂ H′ joining u to v and containing w, of length at most four. This contradicts Theorem 3.2.

3.1.1 Quadrilateral-Free Subgraphs

The results of this section will not be required for any of the subsequent material. A natural question is, given an hexagon-free graph, what is the maximum number of edges in a quadrilateral-free subgraph or a subgraph of girth at least five? Györi [19] proved that every hexagon-free bipartite graph G = (V, E) contains a subgraph with at least \frac{1}{2}|E|+1 edges and no quadrilateral. In the next theorem, we extend this result to hexagon-free graphs which are not necessarily bipartite. In fact, Györi’s theorem follows at once from the fact that all block subgraphs of a bipartite graph are isolated, and the proof which we give below. This contains the proof of Theorem 1.4.

Theorem 3.3 Some set of at least \frac{1}{2}|E| edges of any hexagon-free graph G = (V, E) form a subgraph containing no cycle of length four (respectively, no cycle of length at most four). Equality holds if and only if G is a union of edge-disjoint complete graphs of order five (respectively, complete graphs of order four or five).

Proof. By Theorem 3.1, G admits a decomposition into block subgraphs and a subgraph F no edge of which is in a quadrilateral. We may delete less than half the edges of F to obtain a bipartite subgraph F′ of F of girth at least eight (for example, the expected size of a random cut of F into two equal size parts is \frac{1}{2}|F |, so there is a cut of the required size). For each block subgraph H, by Theorem 3.2, we observe that H contains a spanning subgraph containing no quadrilaterals and with at least \frac{1}{2}|E(H)| edges. Equality holds only if H is a complete graph on five vertices. So, we may delete \frac{1}{2}|E(H)| edges of H to obtain a subgraph H′ of H containing no quadrilaterals. Now F′ together with all subgraphs H′ is a subgraph of G containing no quadrilaterals. Equality holds if and only if F = ∅ and H = K_{5} for every block subgraph H.

To prove Theorem 1.4, i.e. the statements in brackets, observe that every block subgraph contains a spanning subgraph with half its edges and of girth five. Equality holds only if the block subgraph is a complete graph of order four or five. Repeating the above proof with an application of Theorem 3.1, we obtain the required subgraph of girth at least five.

It would be interesting to see if similar arguments work to find, say, a subgraph of girth eight containing a positive proportion of the edges. Also, we remark that for hexagon-free bipartite graphs G, we obtain a subgraph of girth at least eight with at least \frac{1}{2}|E| + k edges, where k is the number isolated block subgraphs in G. Note that all blocks H of G are isolated, and a spanning tree in each such H has \frac{1}{2}|H| + 1 edges.

4 Paths of Length Three

If π is a pair of vertices of V, then |π| denotes the number of paths of length three in G with both endpoints in π. Throughout this section, G(π) is the subgraph of G consisting of the union of all paths of length three with endpoints in π. For a pair π with |π| ≥ 2, we say that G(π) is degenerate if the distance between the vertices of π in G(π) is two, and non-degenerate otherwise. The aim of this section is to find an upper bound for the number of paths of length three in any hexagon-free graph. The number of such paths is precisely ∑_{π∈\binom{V}{2}} |π|. The range of summation will be partitioned into sets and the sums over each of these sets will be estimated. One of the main results (Lemma 4.3) is that the sum over non-degenerate pairs π with |π| ≥ 3 and over degenerate pairs π with |π| ≥ 2 is less than 27Δ|E|, which we consider to be small. This already gives the upper bound

∑_{π∈\binom{V}{2}} |π| < 2\binom{n}{2} + 83Δ|E|.

However, we will improve this bound by showing that Σ = {π : |π| = 1} is large. In particular, we will show (in Lemma 4.6) that in a hexagon-free graph with close to the extremal number of edges, a positive proportion of all pairs of vertices are joined by a unique path of length three.

4.1 Subgraphs Spanned by Paths

To find the maximum possible number of paths of length three in a hexagon-free graph, we first require an analysis of the graphs G(π). We begin with the non-degenerate case:

Lemma 4.1 Suppose G(π) is non-degenerate. Then for some quadrilateral Q(π) or some maximal complete bipartite subgraph K(π), and some pendant edge e(π),

G(π) = \{ \begin{matrix}Q(π) ∪ \{e(π)\} & if |π| = 2 \\ K(π) ∪ \{e(π)\} & if |π| > 2. \end{matrix}

Furthermore, Q(π) and K(π) contain exactly one vertex x ∈ π; the unique vertex of e(π) in Q(π) or K(π) is not adjacent to x; e(π) contains the other vertex y ∈ π; and base(K) ∉ G.

\begin{matrix}\begin{matrix}\begin{aligned}& K(π) ∪ \{e(π)\} \\ Q(π) ∪ \{e(π)\} \end{aligned} & e(π) \\ e(π) \end{matrix} & y \\ y \end{matrix} ; x ; x ; K(π) ; Q(π)

Proof. Let E(π) be the set of edges of G(π) which are not incident with π. Since G contains no hexagon, E(π) is an intersecting family. Therefore E(π) spans a star or a triangle. If E(π) spans a triangle, then |π| ≥ 3 and G(π) has five vertices. Also, each path of length three with endpoints in π contains one edge of the triangle, and two edges incident with π. This implies that some vertex of triangle has degree four in G(π), so G(π) is degenerate, which is a contradiction. Therefore E(π) spans a star, S(π). Now every endvertex of the star is adjacent to exactly one vertex of π, since G(π) is non-degenerate. Suppose that π = {u, v} and that a leaf x of S(π) is adjacent to u and a leaf y of S(π) is adjacent to v. Let w be the centre of the star S(π). By definition of G(π), the edges uw and vw must be present in G(π). However this implies G(π) is degenerate. So every leaf of S(π) is adjacent to u and not v, or every leaf of S(π) is adjacent to v and not u. The vertex w is adjacent to v in the first case, and to u in the second. Thus G(π) has the required structure.

The neighbourhood of a vertex v in G is denoted Γ(v). The closed neighbourhood is Γ[v] = Γ(v) ∪ {v}. Any subgraph H of G is central if V (H) ⊂ Γ[v] for some v ∈ V (H), and we say that v is central for H.

Lemma 4.2 Suppose G(π) is degenerate. Then G(π) is central.

Proof. In the proof of Lemma 4.1, we argued that if E(π) spans a triangle, then some vertex v of the triangle has degree four in G(π). So v is central for G(π). In case E(π) spans a star centered at a vertex w, it is not hard to verify that w is adjacent to both vertices in π, and therefore central for G(π).

4.2 Pairs Joined by Many Paths

Define Π_{1} = \{π ∈ \binom{V}{2} : |π| ≥ 2 and G(π) is degenerate\} and Π_{2} = \{π ∈ \binom{V}{2} : |π| > 2 and G(π) is non-degenerate}, and Π = Π_{1} ∪ Π_{2}. Then Π contains all pairs π with |π| ≥ 3.

Lemma 4.3  ∑_{π∈Π} |π| < 27Δ|E|.

Proof. We will show that the sums over Π_{1} and Π_{2} are less than 25Δ|E| and 2Δ|E| respectively. We begin with Π_{1}. By Lemma 4.2, for each π ∈ Π_{1}, G(π) is central. Therefore we may write

∑_{π∈Π_{1}} |π| ≤ ∑_{v∈V} |P [v]|

where P [v] is the set of paths of length three consisting entirely of vertices of Γ[v]. If E[v] is the set of edges in Γ[v] and E(v) is the set of edges of E[v] not incident with v, then

|P [v]| < 4\binom{|E[v]|}{2} < 2|E[v]|^{2}.

Now, since G is hexagon free, no path of length four consists entirely of edges of E(v). It follows, from well known extremal results for paths [11], that |E(v)| ≤ \frac{3}{2}|Γ(v)| and therefore |E[v]| ≤ \frac{5}{2}|Γ(v)|. Therefore

∑_{π∈Π_{1}} |π| < ∑_{v∈V} \frac{25}{2}|Γ(v)|^{2}
< \frac{25}{2}Δ ∑_{v∈V} |Γ(v)| = 25Δ|E|.

The next task is to deal with Π_{2}. By Lemma 4.1,

∑_{π∈Π_{2}} |π| = ∑_{K⊂G} ∑_{K(π)=K} |π|

where the second sum above is the sum over pairs π for which K = K(π) where K is a maximal complete bipartite graph of G with |K| ≥ 6 and base(K) ∉ E. The number of π ∈ \binom{V}{2} for which K = K(π) is at most 2Δ, since the choice of a pendant edge on K specifies π, by Lemma 4.1. By Theorem 3.2, and since base(K) ∉ G, each K is contained in a block subgraph H of type (1) or (4). By Theorem 3.1, block subgraphs are edge-disjoint so H is uniquely determined by K. In turn, if K = K(π), then |π| = \frac{1}{2}|K| ≤ \frac{1}{2}|H|. Finally, the number of choices of K ⊂ H is at most two, since H has type (1) or (4) and base(K) ∉ G. Therefore

∑_{π∈Π_{2}} |π| < ∑_{H⊂G} ∑_{K⊂H} Δ|H|
< ∑_{H⊂G} 2Δ|H|
< 2Δ ∑_{H⊂G} |H| ≤ 2Δ|E|.

In the penultimate line, we used Theorem 3.1: the block subgraphs of G are edge-disjoint.

4.3 Directed Paths

A maximum directed cut in an oriented graph G is a partition of the vertex set into two sets X and Y such that the number of directed edges from X to Y is as large as possible. This maximum is denoted mdc(G).

Proposition 4.4 Let G be an oriented graph on n vertices with e edges, and suppose that mdc(G) ≤ γe. Then the number of directed paths of length two in G is at least (1 − γ)^{2} \frac{e^{2}}{n}.

The proof of Proposition 4.4 is based on the following numerical inequality:

Lemma 4.5 For n ≥ 1 let V be an n-point set and f, g : V → [0, ∞) be two functions such that ∑_{v∈V} f(v) = ∑_{v∈V} g(v). Then

∑_{v∈V} f(v)g(v) ≥ \frac{1}{n} ( ∑_{v∈V} min\{2f(v) − g(v), f(v)\} )^{2}

Proof. The proof is by induction on n. The inequality is clearly valid for n = 1. Now suppose n > 1, and denote h(v) = g(v) − f(v), I = {v ∈ V : h(v) > 0}. For convenience, we let ∑_{v∈I} h(v) = a and ∑_{v∈V} f(v) = b. Then the required inequality becomes:

∑_{v∈V} f(v)[f(v) + h(v)] ≥ \frac{1}{n}(b − a)^{2}.  (1)

Since f and g have the same sum over V, we observe that ∑_{v∈V} h(v) = 0. Also, we may assume that a < b, since otherwise the required result holds trivially.

Let f and h be functions which minimize the sum in (1) subject to the constraints f ≥ 0 and f + h ≥ 0, and the three constraints

∑_{v∈I} h(v) = a  ∑_{v∈V} h(v) = 0  ∑_{v∈V} f(v) = b.

Set A = {v ∈ V : f(v) = 0} and B = {v ∈ V : f(v) + h(v) = 0}. We may assume that A and B are disjoint sets, since if v ∈ A ∩ B then we may apply the induction hypothesis to V \ {v}. We may also assume that X = V \(A ∪ B) is non-empty, since otherwise

b = ∑_{v∈B} f(v) = − ∑_{v∈B} h(v)) ≤ a,

contradictory to our assumption that a < b. Setting S = ∑_{v∈B} h(v), we find that the restriction of f to X is the global minimizer, among all functions f̃ on X, of

∑_{v∈X} f̃(v)[f̃(v) + h(v)],

subject to the constraints f̃ ≥ 0 and f̃ + h ≥ 0, and ∑_{v∈X} f̃(v) = b + S. Moreover, by construction, the minimizer f|_{X} is in the interior of the polytope defined by these constraints. Hence, there is a Lagrange multiplier λ ∈ ℝ such that for all v ∈ X,

2f(v) + h(v) = λ.  (2)

Using that ∑_{v∈V} h(v) = 0, we find

∑_{v∈X} h(v) = ∑_{v∈V} h(v) − S − T = −S − T,

where T = ∑_{v∈A} h(v). Let m = |X| = n − |A ∪ B|. Summing (2) over v ∈ X, we obtain

f(v) = \frac{2b + S − T}{2m} − \frac{h(v)}{2}.

Now f(v) and h(v) + f(v) are both non-negative, so this gives

|h(v)| ≤ \frac{2b + S − T}{m}

for all v ∈ X. Hence

∑_{v∈V} f(v)[f(v) + h(v)] = ∑_{v∈X} f(v)[f(v) + h(v)] = m (\frac{2b + S − T}{2m} )^{2} − \frac{1}{4} ∑_{v∈X} h(v)^{2}. (3)

We have observed that |h(v)| ≤ (2b+S −T)/m, and note also that ∑_{v∈X} |h(v)| = 2a+S −T, by the definition of A and B. Therefore,

∑_{v∈X} h(v)^{2} ≤ \frac{m(2a + S − T)}{2b + S − T} (\frac{2b + S − T}{m} )^{2} = \frac{(2b + S − T)(2a + S − T)}{m}.

Substitution into (3) gives

∑_{v∈V} f(v)[f(v) + h(v)] ≥ m (\frac{2b + S − T}{2m} )^{2} − \frac{(2b + S − T)(2a + S − T)}{4m}
≥ \frac{(b − a)(2b + S − T)}{2m}
≥ \frac{(b − a)(2b − 2a)}{2n}
≥ \frac{1}{n}(b − a)^{2}.

Here we have used the fact that m ≤ n and S − T ≥ −2a.

Proof of Proposition 4.4. We assume the vertex set of G is V. The number of directed paths of length two is

∑_{v∈V} d^{in}(v)d^{out}(v)

where d^{in}(v) and d^{out}(v) denote the in and out degree of vertex v. Let f(v) = d^{in}(v) and g(v) = d^{out}(v). The assumption on the size of the maximum directed cut implies

∑_{v∈I}[g(v) − f(v)] = a

for some a ≤ γe, where I = {i : g(v) > f(v)}. Also ∑_{v∈V} f(v) = e = ∑_{v∈V} g(v). By Lemma 4.5,

∑_{v∈V} f(v)g(v) ≥ \frac{1}{n}(e − a)^{2} ≥ \frac{1}{n}(1 − γ)^{2}e^{2}.

4.4 Pairs Joined by a Unique Path

We are now prepared to establish a lower bound for the number of pairs of vertices in a hexagon-free graph which are joined by exactly one path of length three. Let Σ be this set of pairs. Let us define an extension in an oriented graph to be any path of length three which contains a directed path of length two from one of its endpoints. The set of pairs of endpoints of such paths will be denoted by Σ⃗.

Lemma 4.6 Let G be a hexagon-free graph with no cut of size more than γ|E|. Then there exists an orientation of G such that |Σ⃗\Σ| < 31Δ|E|. In particular, if the number of vertices of degree less than d in G is at most D, then

|Σ| > (1 − γ)^{2} \frac{d|E|^{2}}{n} − 31Δ|E| − d^{2}DΔ.

Proof. The second claim follows from the first as follows. The number of directed paths of length two which cannot be extended to a path of length three in at least d − 2 ways is at most dDΔ, since there are D choices for the end vertex of the directed path, at most d choices for the edge adjacent to the end vertex and at most Δ choices for the remaining edge. Proposition 4.4 provides at least (1 − γ)^{2} \frac{|E|^{2}}{n} − dDΔ directed paths of length two in G which can be extended in at least d − 2 ways. Hence

|Σ| ≥ ((1 − γ)^{2} \frac{|E|^{2}}{n} − dDΔ) (d − 2) − |Σ⃗ \ Σ| > (1 − γ)^{2} \frac{d|E|^{2}}{n} − 31Δ|E| − d^{2}DΔ.

Now the orientation of G is described as follows: by Theorem 3.1, G admits a decomposition into block subgraphs and a quadrilateral-free graph F. The edges of F and of every isolated quadrilateral are oriented arbitrarily. The edges in every non-quadrilateral block subgraph H are oriented so that every vertex of degree two has indegree two. These orientations for type (2) and (3) block subgraphs are shown below:

By Lemma 4.3, |Π| < 27Δ|E|. Let

Σ′ = {π ∈ Σ⃗ : |π| = 2 and G(π) is non-degenerate}.

Let π ∈ Σ′. By Lemma 4.1, G(π) = Q(π)∪{e(π)}. Let π = {u, v} and V (Q(π)) = {u, x, w, y}, and e(π) = {w, v}. By Theorem 3.1, Q(π) is contained a unique block subgraph H(π).

Furthermore u and w have degree two in H and {u, v} ∉ H, otherwise by inspection of the four types of block subgraphs, G(π) would be degenerate or |π| ≥ 3. We conclude that Q(π) has the orientation

y → w ← x → u ← y.

Now suppose H(π) ≠ Q(π). Then since π is the pair of endpoints of an extension, there is a directed path of length two in G(π) from u or from v. It follows that

u → x → w or v → w → x.

This contradicts the orientation of Q(π). So H(π) = Q(π) for each π ∈ Σ′ – i.e. H is an isolated quadrilateral. Since G contains at most |E|/4 isolated quadrilaterals, and each contributes less than 4Δ pairs to |Σ′|, we have |Σ′| < Δ|E|. Finally,

|Σ⃗\Σ| < |Π| + |Σ′| < 28Δ.

This completes the proof.

5 A Hölder-Type Matrix Inequality

In this section, we give a lower bound for the number of paths of length three in any graph G of maximum degree Δ, and in any m by n bipartite graph of maximum degree Δ. If A is the adjacency matrix of G, and v is the constant vector (1, 1, …, 1), then \frac{1}{2} ⟨A^{3}v, v⟩ is the number of walks of length three in G. Blakley and Roy [5] proved the following Hölder-type inequality for non-negative symmetric matrices S:

⟨Sw, w⟩^{k} ≥ ⟨Sw, w⟩^{k}

for any non-negative unit vector w and any positive integer k. Applying this with w = v/\sqrt{n} and S = A, we deduce that the number of walks of length three in G is at least 4|E|^{3}/n^{2}. It is not hard to show that at most 4Δ|E| + |E| walks of length three are not paths of length three. Therefore we have the following theorem:

Theorem 5.1 Let G be a graph of maximum degree Δ. Then the number of paths of length three in G is at least 4|E|^{3}/n^{2} − 4Δ|E| − |E|.

More recently, Alon, Hoory and Linial [1] showed (using different techniques) that the number of non-returning walks of length k in any graph G is at least \frac{1}{2}(d−1)^{k}n where d is the average degree of G. This gives a similar bound to the one in Theorem 5.1.

Sidorenko [31] proved a bipartite version of the Blakley-Roy inequality: if A is an m by n matrix, A^{∗} denotes the transpose of A, and ∥A∥_{1} is the sum of the entries of A, then ∥AA^{∗}A∥_{1} ≥ ∥A∥_{1}^{3}/(mn). Applying this with A the incidence matrix of an m by n bipartite graph, we obtain:

Theorem 5.2 Let G be an m by n bipartite graph of maximum degree Δ. Then the number of paths of length three in G is at least |E|^{3}/(mn) − 4Δ|E| − |E|.

6 A Regularization Lemma

In all the results so far, there is an explicit dependence on Δ, the maximum degree of our graph. In this section, we will show that extremal hexagon-free graphs cannot be too far from regular:

Lemma 6.1 Let G = (V, E) be an n-vertex C_{2k}-free graph. Then there is an absolute constant c < (32)^{2k/(k−1)} such that for every integer Δ > 1 and k > 2, there is a subgraph G̃ = (V, Ẽ) of G of maximum degree at most Δ with:

|Ẽ| ≥ |E| − c (\frac{n^{\frac{k+1}{k−1}}}{Δ^{\frac{k+1}{k−1}}} ) − cn for k odd.

|Ẽ| ≥ |E| − c (\frac{n^{\frac{k}{k−2}}}{Δ^{\frac{k+2}{k−2}}} ) − cn for k even.

For k = 2, there is a spanning subgraph G̃ of G, of maximum degree c\sqrt{n} and of size at least |G| − cn.

In addition, a bipartite version of this lemma is required. The proof of this bipartite version is omitted, as is along the same lines as the proof of Lemma 6.1.

Lemma 6.2 Let G = (L, R, E) be an m × n C_{2k}-free bipartite graph. Then there is an absolute constant c < (32)^{2k/(k−1)} such that, for every two integers Δ_{L}, Δ_{R} > 4k, G contains a spanning subgraph G̃ = (V, Ẽ) such that the degree in G̃ of every vertex in L is at most Δ_{L}, the degree in G̃ of every vertex in R is at most Δ_{R},

|Ẽ| ≥ |E| − c (\frac{m^{\frac{k+1}{k−1}}}{ΔR^{\frac{k+1}{k−1}}} + \frac{n^{\frac{k+1}{k−1}}}{ΔL^{\frac{k+1}{k−1}}} ) − c(m + n),

for odd k and, for even k > 2:

|Ẽ| ≥ |G| − (32k)^{\frac{2k}{k−1}} (\frac{m^{\frac{k}{k−2}}}{ΔR^{\frac{k+2}{k−2}}} + \frac{n^{\frac{k}{k−2}}}{ΔL^{\frac{k+2}{k−2}}} ) − c(m + n).

The proofs of Lemmas 6.1 and 6.2 use the following result from [26] and [34]:

Proposition 6.3 For every n, k ≥ 2, ex(n, C_{2k}) < 8(k − 1)n^{1+ \frac{1}{k}}. Moreover, for every m, n, k ≥ 2,

ex(m, n, C_{2k}) < \{ \begin{matrix}8(k − 1)(mn)^{\frac{1}{2} + \frac{1}{2k}} + 4(k − 1)(m + n) & for k odd. \\ 8(k − 1)m^{\frac{1}{2} + \frac{1}{k}} \sqrt{n} + 4(k − 1)(m + n) & for k even. \end{matrix}

To prove Lemma 6.1, the following preliminary lemma is required.

Lemma 6.4 Let S_{t} ⊂ V denote the set of vertices of degree at least t in G. Then

|S_{t}| ≤ (32k)^{\frac{2k}{k−1}} max \{\frac{n^{\frac{k+1}{k−1}}}{t^{\frac{2k}{k−1}}} , \frac{n}{t}\} .

Proof. Throughout the proof we write e(A, B) for the number of edges in G with one end in A and one end in B, and e(A) for the number of edges induced by A. Let m = |S_{t}|. When t < 16km^{1/k}, the above inequality reduces to the trivial inequality m < 2^{2k}k − 1n. So we assume that t ≥ 16km^{1/k}. By Proposition 6.3, e(S_{t}, S_{t}) < 8km^{1+ \frac{1}{k}}. It follows that the number of edges between S and V \ S in G is at least

mt − 2e(S_{t}, S_{t}) > mt − 8km^{1+ \frac{1}{k}} > \frac{mt}{2}.

On the other hand, another application of Proposition 6.3 implies that

e(S_{t}, V \S_{t}) < 8k(mn)^{\frac{1}{2} + \frac{1}{2k}} + 8kn.

Hence:

\frac{mt}{2} < 8k(mn)^{\frac{1}{2} + \frac{1}{2k}} + 4kn ⟹ mt < 2k max \{16(mn)^{\frac{1}{2} + \frac{1}{2k}} , 16n\} ,

which implies the required result.

Proof of Lemma 6.1. Suppose first that k is odd. It is enough to prove the lemma with c = (32)^{2k/(k−1)}. Let d be the integer part of n^{2/(k+1)}. It is enough to prove the result for Δ ≤ d, since we could then apply the case Δ = d for larger Δ. We write e(A) for the number of edges induced by a set A and e(A, B) for the number of edges with one end in A and one end in B. Set S = S_{d+1} and m = |S|. By Lemma 6.4, m < cn^{(k−1)/(k+1)}. By Proposition 6.3, it follows that the number of edges in G which contain a vertex in S satisfies:

e(S) + e(S, V \ S) < 8km^{1+1/k} + 8k(mn)^{1/2+1/2k} − 8k(m + n) < cn.

We now greedily delete edges from G. First delete edges incident with a least one vertex of S. Then start with the set of vertices of G of degree d. In general, having reached a subgraph of G of maximum degree t < d, delete one edge per vertex with degree t. Continuing this procedure d − Δ times, we obtain a spanning subgraph G̃ = (V, Ẽ) of G, of maximum degree at most Δ. The size of G̃ can be bounded from below as follows:

|Ẽ| > |E| − ∑_{t=Δ+1}^{d} |S_{t}| − cn

> |E| − c [ ∑_{t=Δ+1}^{∞} \frac{n^{\frac{k+1}{k−1}}}{t^{\frac{2k}{k−1}}} ] − cn
> |E| − cn^{\frac{k+1}{k−1}} ∫_{Δ}^{∞} \frac{1}{t^{\frac{2k}{k−1}}} dt − cn
> |E| − c (\frac{n^{\frac{k+1}{k−1}}}{Δ^{\frac{k+1}{k−1}}} ) − cn.

This completes the proof for k odd. The proof for even k is exactly the same.

7 Proof of Theorems 1.1 and 1.2

Throughout this section, c = (96)^{3} is the constant in Lemma 6.1 with k = 3.

Proof of Theorem 1.2 We proceed by contradiction. Suppose G = (L, R, E) is a hexagonfree bipartite graph with |L| = m, |R| = n and

|E| > 2^{1/3}(mn)^{2/3} + (c + 100)(m^{8/9}n^{2/9} + m^{2/9}n^{8/9} + m + n).

We begin by applying Lemma 6.2, with

Δ_{L} = ⌈\frac{n^{5/9}}{m^{1/9}} ⌉ and Δ_{R} = ⌈\frac{m^{5/9}}{n^{1/9}} ⌉

to obtain a graph G̃ = (L, R, Ẽ) with

|Ẽ| > 2^{1/3}(mn)^{2/3} + 100(m^{8/9}n^{2/9} + m^{2/9}n^{8/9} + m + n).

Let Δ be the maximum of Δ_{R} and Δ_{L}. By Theorem 5.2 and Lemma 4.3,

\frac{|Ẽ|^{3}}{mn} − 4Δ|Ẽ| − |Ẽ| < ∑_{π∉Π} |π| + ∑_{π∈Π} |π| < 2mn + 27Δ|Ẽ|.

This cubic inequality in |Ẽ| gives

|Ẽ| < 2^{1/3}(mn)^{2/3} + 100Δ(mn)^{1/3}
< 2^{1/3}(mn)^{2/3} + 100(m^{8/9}n^{2/9} + m^{2/9}n^{8/9} + m + n).

This contradiction completes the proof.

Proof of Theorem 1.1 To prove Theorem 1.1, we will proceed somewhat indirectly by showing first that if G = (V, E) is an n-vertex of maximum degree at most Δ = n^{4/9}, and with

|E| > λn^{4/3} + 4cn^{7/6} + cn,

then G contains a hexagon. Let us see that this is sufficient to prove Theorem 1.1. Assume we have proved this statement. Take any hexagon-free graph G = (V, E) on n vertices, with |E| > λn^{4/3} + 5cn^{7/6} + cn. Then there is a subgraph G̃ = (V, Ẽ) of G of maximum degree at most Δ (by Lemma 6.1), and such that

|Ẽ| > |E| − cn^{7/6} − cn > λn^{4/3} + 4cn^{7/6}.

It follows, from the assumption, that G̃ contains a hexagon, as required.

Now suppose G = (V, E) is any n-vertex graph of maximum degree at most n^{4/9}, with |E| > λn^{4/3} + 4cn^{7/6}, and that any graph on m < n vertices of maximum degree at most m^{4/9} with more than λm^{4/3} + 4cm^{7/6} edges contains a hexagon. We can assume |E| = ⌊λn^{4/3} + 4cn^{7/6} + 1⌋, by deleting some edges from G. If G contains at least D = ⌊n^{1/2}⌋ vertices of degree less than d = \frac{4}{3}λn^{1/3} − cn^{1/6}, then we delete D vertices of degree less than d from G to obtain an m-vertex graph G′ = (V′, E′) with

|E′| > λm^{4/3} + 4cn^{7/6} + cn^{2/3}.

The number of vertices of degree more than m^{4/9} in G′ is at most cn^{2/3}, by Lemma 6.4. Deleting at most one edge on each of these vertices, we arrive at a graph G′′ = (V′, E′′) on m vertices with

|E′′| > λm^{4/3} + 4cm^{7/6}.

Furthermore, the maximum degree in G′′ is at most m^{4/9}, since n^{4/9} ≤ m^{4/9}+1. By induction, G′′ contains a hexagon, which is a contradiction. So, we may assume that at most D vertices of G have degree less than d.

By Theorem 1.2, the maximum cut in G has size at most

max_{0≤k≤n} 2^{1/3}[k(n − k)]^{2/3} + 4cn^{10/9} < \frac{1}{2λ}|E|.

By Lemma 4.6, applied with γ = \frac{1}{2λ}, D = ⌊n^{1/2}⌋, d = \frac{4}{3}λn^{1/3} − cn^{1/6} and Δ = n^{4/9}, we obtain

|Σ| > (1 − γ)^{2} \frac{d|E|^{2}}{n} − 87Δ|E| − d^{2}DΔ
> (1 − γ)^{2} \frac{4|E|^{3}}{3n} − \frac{6cn^{1/6}|E|^{2}}{n} − 33Δ|E|.

Therefore, by Theorem 5.1 and Lemma 4.3,

\frac{4|E|^{3}}{n^{2}} − 4Δ|E| − |E| < ∑_{|π|=1} |π| + ∑_{|π|=2} |π| + ∑_{|π|>2} |π|
< n^{2} − |Σ| + 27Δ|E|
< n^{2} − (1 − γ)^{2} \frac{4|E|^{3}}{3n^{2}} + \frac{6cn^{1/6}|E|^{2}}{n} + 60Δ|E|.

This gives the cubic inequality

\frac{1}{3λ^{3}} (16λ^{3} − 4λ^{2} + λ − 3)|E|^{3} + λ^{−3}|E|^{3} − n^{4} − 5cn^{7/6}|E|^{2} − 65Δ|E|n^{2} < 0.

Since n^{4} ≥ λ^{−3}(|E| − 4cn^{7/6} − 1)^{3}, we obtain

\frac{1}{3λ^{3}} (16λ^{3} − 4λ^{2} + λ − 3)|E|^{3} + cn^{7/6}|E|^{2} − 65Δ|E|n^{2} < 0.

Since 16λ^{3} − 4λ^{2} + λ − 3 = 0, the first term above is zero, and as c = (96)^{3}, the rest of the expression is positive, which is a contradiction.

8 Appendix: Classification of Block Subgraphs

The theorem we wish to prove is the following:

Theorem 3.2. Let H be a block subgraph of a hexagon-free graph. Then H has type (1), or H is a strongly induced subgraph of type (2), (3) or (4).

To prove this theorem, we will first show that type (2), (3) and (4) subgraphs are strongly induced subgraphs. It then remains to show that if a block subgraph H does not have type (1), then it has type (2), (3) or (4). We begin with the first task.

Lemma 8.1 Let H be a block subgraph of type (2), (3) or (4). Then H is a strongly induced subgraph of G.

Proof. We are required to show that if P is a path with both endpoints in H and |E(P)| ≤ 4, then P ⊂ H. We deal first with the case 2 ≤ |E(P)| ≤ 4. Suppose, for a contradiction, that P ⊄ H. We may assume E(P) ∩ E(H) = ∅ and let V (P) ∩ V (H) = {u, v}. By inspection of subgraphs of types (2), (3) and (4), there is a path P′ ⊂ H, of length 6 − |E(P)|, with endpoints {u, v}, unless |E(P)| = 2, and {u, v} is the neighbourhood of a vertex of degree two in H, and H has type (2) or (3). But if H has type (2) or (3), then H ∪ P contains an additional neighbour of {u, v}, namely the midpoint of P. This contradicts the fact that H contains all common neighbours of {u, v}. Thus we have produced a path P′ ⊂ H with |E(P)∪E(P′)| = 6, contradicting that G is hexagon-free. Therefore P ⊂ H if 2 ≤ |E(P)| ≤ 4, as required. If |E(P)| = 1 and H is a block subgraph with P ⊄ H, then there is an edge e of G joining two vertices of H, and H ∪ {e} contains a quadrilateral Q, which contains e. By definition, Q is contained in some maximal complete bipartite subgraph K ⊂ G, which, by inspection, intersects every maximal complete bipartite subgraph of H, since H has type (2), (3) or (4). This contradiction completes the proof.

Proof of Theorem 3.2 Let H be a non-isolated block subgraph i.e. a block subgraph which is not of type (1). By definition, H is the union of a maximal intersecting family K = {K_{1}, K_{2}, …, K_{r}}, where r ≥ 2. We consider first the case that all K_{i} are quadrilaterals. In this case, K_{i} and K_{j} always have at least three vertices in common, since otherwise G contains a hexagon. If |V (K_{i}) ∩ V (K_{j})| = 4 for all i and j, then V (K_{i}) = V (K_{j}) for all i and j, implying H = K_{4} which is of type (3). Otherwise, without loss of generality, we may assume |V (K_{1}) ∩ V (K_{2})| = 3. This implies K_{1} ∪ K_{2} has five vertices and is a type (2) subgraph of G, due to the maximality of K_{1} and K_{2}. Now, for any i ≥ 3, E(K_{i})∩E(K_{1}) ≠ ∅. Suppose {u, v} ∈ E(K_{i}) ∩ E(K_{1}). By Lemma 8.1, all paths of length two, three or four in K_{i} joining u and v are contained in K_{1} ∪ K_{2}. It follows that K_{i} ⊂ K_{1} ∪ K_{2}, implying that H ⊂ K_{1} ∪ K_{2}. Let x and y be vertices of degree exactly two in K_{1} ∪ K_{2}. If u and v are adjacent in some K_{i}, then H has type (4). Otherwise H has type (2) or (3). This completes the proof for the case that all of the K_{i} are quadrilaterals.

Assume K_{1} is not a quadrilateral, and let Q_{2} ⊂ K_{2} be a quadrilateral intersecting a quadrilateral Q_{1} ⊂ K_{1} in at least one edge. If V (Q_{2}) = V (Q_{1}) for some quadrilateral Q_{1} ⊂ K_{1}, then K_{1} ∪ Q_{2} is a type (3) subgraph, due to the maximality of K_{1}. By Lemma 8.1, applied as in the first part of the proof, K_{i} ⊂ K_{1} ∪ Q_{2} for all i ≥ 2. If H = K_{1} ∪ Q_{2}, then H has type (3) as required (and K = {K_{1}, K_{2}, K_{3}}). Otherwise let e be an edge in H but not in K_{1} ∪ Q_{2}. Then, by inspection, |V (K_{1})| = 5, since otherwise G contains a hexagon in K_{1} ∪ Q_{2} ∪ {e}. It follows that H is of type (4). The remaining case is |V (Q_{2}) ∩ V (Q_{1})| = 3 for any pair of intersecting quadrilaterals Q_{1} ⊂ K_{1} and Q_{2} ⊂ K_{2}. In this case, K_{1} ∪ K_{2} has type (2). As before, using Lemma 8.1, we deduce that V (H) ⊂ V (K_{1}) ∪ V (K_{2}). If H = K_{1} ∪ K_{2}, then H has type (2) and we are done. Otherwise let e be an edge of H not in K_{1} ∪ K_{2}. If K_{2} is not a quadrilateral, then K_{1} ∪ K_{2} ∪ {e} contains a hexagon, on inspection of type (2) subgraphs. So K_{2} must be a quadrilateral. In that case, K_{1} ∪ K_{2} ∪ {e} has type (3) and (as above) H has type (3).

References

[1] Alon, N. Hoory, S. Linial, N. The Moore bound for irregular graphs. Graphs Combin. 18 (2002), no. 1, 53–57.

[2] Alon, N., Spencer, J. H. The probabilistic method. Second edition. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience [John Wiley & Sons], New York, 2000.

[3] Benson, C. T. Minimal regular graphs of girths eight and twelve. Canad. J. Math. 18 1966 1091–1094.

[4] Biggs, N. Algebraic graph theory. Second edition. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1993. viii.

[5] Blakley, G., Roy, P. A Hölder type inequality for symmetric matrices with nonnegative entries. Proc. Amer. Math. Soc. 16 1965 1244–1245.

[6] Bollobás, B. Extremal Graph Theory. In Handbook of Combinatorics (edited by R.L. Graham, M. Grötschel, L. Lovász), 1231-1292, North-Holland, Amsterdam, 1995.

[7] Bondy, J.A., Simonovits, M. Cycles of even length in graphs. J. Combin. Theory Ser. B, 16, 87-105 (1974).

[8] Chung, F., Graham, R., Sparse quasi-random graphs. Special issue: Paul Erdős and his mathematics. Combinatorica 22 (2002), no. 2, 217–244.

[9] de Caen, D., Székely, L.A. The maximum size of 4- and 6-cycle free bipartite graphs on m, n vertices. Sets, graphs and numbers (Budapest, 1991), 135-142, Colloq. Math. Soc. János Bolyai, 60, Noth-Holland, Amsterdam, 1992.

[10] Erdős, P. Some recent results on extremal problems in graph theory. Results. 1967 Theory of Graphs (Internat. Sympos., Rome, 1966) pp. 117–123 pp. 124–130, Gordon and Breach, New York; Dunod, Paris.

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

[12] Erdős, P., Rényi, A., Sós, V. T. On a problem of graph theory. Studia Sci. Math. Hungar. 1 1966 215–235.

[13] Erdős, P. Simonovits, M. A limit theorem in graph theory. Studia Sci. Hungar. 1, 51-57 (1966).

[14] Erdős, P., Simonovits, M. Compactness results in extremal graph theory. Combinatorica 2 (1982), no. 3, 275–288.

[15] Feit, W., Higman, G. The nonexistence of certain generalized polygons. J. Algebra 1 1964 114–131.

[16] Füredi, Z. On the number of edges of quadrilateral-free graphs. J. Combin. Theory Ser. B 68 (1996), no. 1, 1–6.

[17] Füredi, Z. Unpublished manuscript.

[18] Füredi, Z. Turán-type problems. Surveys in combinatorics, 1991 (Guildford, 1991), 253– 300, London Math. Soc. Lecture Note Ser., 166, Cambridge Univ. Press, Cambridge, 1991.

[19] Györi, E. C_{6}-free bipartite graphs and product representation of squares. Graphs and combinatorics (Marseille, 1995). Discrete Math. 165/166 (1997), 371–375.

[20] Kollár, J, Rónyai, L, Szabó, T. Norm-graphs and bipartite Turn numbers. Combinatorica 16 (1996), no. 3, 399–406.

[21] Kövari, T., Sós, V., Turán, P. On a problem of K. Zarankiewicz. Colloquium Math. 3, (1954). 50–57.

[22] Kühn, D., Osthus, D. 4-Cycles in graphs with forbidden even cycles. Preprint (2003).

[23] Lubotzky, A., Phillips, R., Sarnak, P. Ramanujan graphs. Combinatorica 8 (1988), no. 3, 261–277.

[24] Lazebnik, F., Ustimenko, V. A., Woldar, A. J., A new series of dense graphs of large girth. Bull. Amer. Math. Soc. 32(1), 73-79 (1995).

[25] Lazebnik, F., Ustimenko, V. A., Woldar, A. J., Polarities and 2k-cycle-free graphs. Discrete Math. 197/198 (1999), 503–513.

[26] Naor, A., Verstraëte, J. A. A Note on Bipartite Graphs without 2k-Cycles. Preprint (2003).

[27] Peykre, L. P. An automorphism of the geometry of the group B_{2}(2^{n}) as a polynomial mapping, Ukrainian Math. J., v. 44, no. 11 (1992), 1530–1534 (in Russian).

[28] Reiman, I. Über ein problem von Zarankiewicz, Acta Acad. Sci. Hungar. 9 (1958), 269-279.

[29] Sárkőzy, G. Cycles in bipartite graphs and an application in number theory. J. Graph Theory 19 (1995), no. 3, 323–331.

[30] Simonovits, M. A method for solving extremal problems in graph theory, stability problems. 1968 Theory of Graphs (Proc. Colloq., Tihany, 1966) pp. 279–319 Academic Press, New York

[31] Sidorenko, A. F. Inequalities for functionals generated by bipartite graphs. (Russian) Diskret. Mat. 3 (1991), no. 3, 50–65; translation in Discrete Math. Appl. 2 (1992), no. 5, 489–504

[32] Tits, J., Théorème de Bruhat et sous-groupes paraboliques. C. R. Acad. Sci. Paris 254 (1962), 2910–2912.

[33] Turán, P. On an extremal problem in graph theory. (in Hungarian), Mat. Fiz. Lapok 48, 436-452, 1941.

[34] Verstraëte, J. A. Arithmetic progressions of cycle lengths in graphs. Combin. Probab. Comput 9 (2000) no 4. 369–373.

[35] Wenger, R. Extremal graphs with no C^{4}’s, C^{6}’s, or C^{10}’s. J. Combin. Theory Ser. B 52 (1991), no. 1, 113–116.