Planar Graphs with the Maximum Number of Induced 4-Cycles or 5-Cycles

An important class of problems in extremal graph theory concerns determining the maximum number of induced copies of a small graph H that can be contained in a graph on n vertices. These questions were first considered by Pippenger and Golumbic in [19] where they showed among other things that for every k-vertex graph H, the maximum number of induced copies of H in an n-vertex graph is asymptotically at least \(\frac{n^k}{k^k-k}\). The maximum is now known asymptotically for all graphs H on at most four vertices except the path of length 3, as well as for certain complete partite graphs. See [6] and its references for a good summary of these results, and see [14] and [22] for some results for other graphs H.

The case where H is a cycle has received particular attention. Pippenger and Golumbic conjectured in their paper that the lower bound stated above is asymptotically tight for cycles of length at least 5. This conjecture was verified for 5-cycles by Balogh, Hu, Lidický, and Pfender in [2], where they determined exactly the maximum number of induced 5-cycles in a graph on n vertices when n is large. The best upper bound known for general cycles is due to Král’, Norin, and Volec in [16], who showed that for all n and \(k\ge 5\), every n-vertex graph contains at most \(2n^k/k^k\) induced k-cycles.

A closely related problem is to determine the maximum number of induced copies of H that can be contained in a planar graph on n vertices. We will write \(f_I(n,H)\) for this quantity and f(n, H) for the corresponding quantity when the copies of H do not have to be induced.

We consider in particular the case where H is a small cycle. Hakimi and Schmeichel showed in [13] that \(f(n,C_3)=3n-8\) for \(n\ge 3\), and \(f(n,C_4)=\frac{1}{2}(n^2+3n-22)\) for \(n\ge 4\). Since a 3-cycle in a graph is always induced, this gives \(f_I(n,C_3)=3n-8\). Also, it is straightforward to see that the complete bipartite graph \(K_{2,n-2}\) contains \(\frac{1}{2}(n^2-5n+6)\) induced 4-cycles, so \(f_I(n,C_4)=\frac{1}{2}n^2+O(n)\), as observed in [7]. In [11] Győri, Paulos, Salia, Tompkins, and Zamora determined \(f(n,C_5)\) exactly for all \(n\ge 5\), showing that \(f(n,C_5)=2n^2-10n+12\) for \(n\ge 8\), and in [7] Ghosh, Győri, Janzer, Paulos, Salia, and Zamora showed that \(f_I(n, C_5)=\frac{1}{3}n^2 +O(n)\).

In [3] and [4] Cox and Martin determined f(n, H) asymptotically when H is a small even cycle, showing that \(f(n,C_{2k})=\left( \frac{n}{k}\right) ^k+o(n^k)\) for \(k\in \{3,4,5,6\}\). For \(n\equiv 0\pmod {k}\), the graph \(G_{n,k}\) defined by replacing every second vertex in a 2k-cycle with \(\frac{n}{k}-1\) copies of that vertex contains \((\frac{n}{k}-1)^k\) induced 2k-cycles, hence also \(f_I(n,C_{2k})= \left( \frac{n}{k}\right) ^k+o(n^k)\) for \(k\in \{3,4,5,6\}\). Cox and Martin go on to conjecture that \(f(n,C_{2k})=\left( \frac{n}{k}\right) ^k+o(n^k)\) for all \(k\ge 7\), which if true would similarly determine \(f_I(n,C_{2k})\) asymptotically for all \(k\ge 7\).

Much less is known for odd cycles of length greater than 5. In the same spirit as above, by evenly blowing up k pairwise non-adjacent vertices in a \((2k+1)\)-cycle until the graph has approximately n vertices, one can obtain a lower bound of \(\left( \frac{n}{k}\right) ^k+o(n^k)\) for \(f_I(n,C_{2k+1})\) for all \(k\ge 1\). One can obtain a slightly better lower bound for \(f(n,C_{2k+1})\) by adding a path through each of the blown up sets of vertices in the graph \(G_{n,k}\) defined above to obtain a planar graph containing \(2k\left( \frac{n}{k}\right) ^k+o(n^k)\) non-induced copies of \(C_{2k+1}\). These blow-up constructions were first given in [9] and [12], and were also considered in [3] and [4]. Hakimi and Schmeichel showed in [13] that \(f(n,C_{2k+1})=O(n^k)\), and this seems to be the best known upper bound.

For results on f(n, H) for various other graphs H see [1, 3, 5, 9, 10, 20], and [21]. In the general case, Huynh, Joret, and Wood proved a far-reaching result in [15] which gives the order of magnitude of f(n, H) for all H in terms of a graph parameter called the ‘flap-number’ of H. Very recently, in [17], Liu showed (Corollary 6.1 in that paper) that for all graphs H, \(f_I(n,H)=\varTheta (f(n,H))\), thus determining the order of magnitude of \(f_I(n,H)\) for all H.

In this paper we will determine \(f_I(n,C_4)\) and \(f_I(n,C_5)\) exactly for large n, and will identify the graphs which exhibit these maxima. Our result for 4-cycles is the following.

Theorem 1

For large n, \(f_I(n,C_4)=\frac{1}{2}(n^2-5n+6)\). Moreover, for large n, the only n-vertex planar graph which contains \(f_I(n,C_4)\) induced 4-cycles is the complete bipartite graph \(K_{2,n-2}\).

Turning to the 5-cycle case, we first define a family of graphs which we will show to be the only n-vertex planar graphs containing \(f_I(n,C_5)\) induced 5-cycles for large n.

Definition 1

A graph G on \(n\ge 19\) vertices is of the required form if it contains distinct vertices \(u_1\), \(u_2\), \(u_3\), and w such that the remainder of its vertices can be partitioned into sets \(A=\{a_1,\dots ,a_{|A|}\}\), \(B=\{b_1,\dots ,b_{|B|}\}\), \(C=\{c_1,\dots ,c_{|C|}\}\), and \(Z=\{z_1,\dots ,z_6\}\) such that all of the following hold:

1. (1)
   1. (a)

      if \(n\equiv 1 \pmod {3}\), then \(|A|=|B|=\frac{n-7}{3}\) and \(|C|= \frac{n-16}{3}\),

   2. (b)

      if \(n\equiv 2 \pmod {3}\), then \(|A|=\frac{n-5}{3}\), \(|B|=\frac{n-8}{3}\), and \(|C|=\frac{n-17}{3}\), or \(|A|=|B|=\frac{n-8}{3}\) and \(|C|=\frac{n-14}{3}\),

   3. (c)

      if \(n\equiv 0 \pmod {3}\), then \(|A|=\frac{n}{3}-2\), \(|B|=\frac{n}{3}-3\), and \(|C|=\frac{n}{3}-5\), or \(|A|=|B|=\frac{n}{3}-2\) and \(|C|=\frac{n}{3}-6\),

2. (2)

   the edge set of G contains the edges \(u_1u_2\), \(u_1u_3\), \(u_2u_3\), \(u_1z_1\), \(u_2z_1\), \(u_1z_2\), \(u_2z_4\), \(z_1z_2\), \(z_1z_3\), \(z_1z_4\), \(z_2z_3\), \(z_3z_4\), \(z_2w\), \(z_3w\), \(z_4w\), \(u_2z_5\), \(u_3z_5\), \(z_5w\), \(u_1z_6\), \(u_3z_6\), and \(z_6w\), and the edges in the three complete bipartite graphs with vertex classes \(\{u_1,w\}\) and A, \(\{u_2,w\}\) and B, and \(\{u_3,w\}\) and C, and

3. (3)

   the remaining edges of G are taken from \(a_{|A|}z_2\), \(z_4b_1\), \(b_{|B|}z_5\), \(z_5c_1\), \(c_{|C|}z_6\), \(z_6a_1\), \(a_ia_{i+1}\) for \(1\le i\le |A|-1\), \(b_ib_{i+1}\) for \(1\le i\le |B|-1\), and \(c_ic_{i+1}\) for \(1\le i\le |C|-1\).

We refer to the edges in point 3 of Definition 1 as optional edges of a graph of the required form, and if none of these edges are present then we say that G is a principal graph of the required form. An illustration of a general graph of the required form is given in Fig. 1. In this illustration red lines represent optional edges. A graph of the required form is clearly planar. It is interesting to note that a graph of the required form in which all optional edges are present is a maximal planar graph.

Roughly speaking, a large graph of the required form is built from a smaller graph of the required form with \(n\equiv 1\pmod {3}\) vertices by “adding vertices to A, B, and C as evenly as possible”. If the number of vertices in the smaller graph has some other value modulo 3, then we need to add the first one or two vertices to particular classes before adding the rest as evenly as possible.

In a large graph of the required form almost all of the vertices are in A, B, or C. For each \(a\in A\) and \(b\in B\) the cycle \(u_1awbu_2\) is an induced 5-cycle in the graph. Similarly, there is an induced 5-cycle containing each pair of vertices \(b\in B\) and \(c\in C\), and each pair \(a\in A\) and \(c\in C\). Since these 5-cycles are different for different pairs of vertices, and each of A, B, and C has size \(\frac{1}{3}n-O(1)\), this accounts for \(3(\frac{1}{3}n-O(1))^2=\frac{1}{3}n^2+O(n)\) induced 5-cycles in G.

Theorem 2

For large n,

Moreover, for large n, if G is a planar graph on n vertices, then G contains \(f_I(n,C_5)\) induced 5-cycles if and only if G is of the required form.

The conclusion of Theorem 2 does not hold for all n. Indeed, for \(n=10\) Theorem 2 would assert that no planar graph on 10 vertices contains more than 14 induced 5-cycles, but the graph shown in Fig. 2 contains 16. In this figure, the colours are only intended to highlight the structure of the graph.

For longer cycles we make the following conjecture based on the constructions given above.

Conjecture 1 For \(k\ge 6\) and n sufficiently large relative to k, the n-vertex graph obtained by blowing up \(\left\lfloor { \frac{k}{2} }\right\rfloor \) pairwise non-adjacent vertices in a k-cycle to sets of as equal size as possible contains the largest number of induced k-cycles of any planar graph.

It would also be interesting to know how many induced k-cycles can be contained in an n-vertex graph which can be embedded in a fixed surface other than the sphere.

Question 1

For each \(k\ge 3\) and each surface \(\varSigma \) other than the sphere, what is the maximum number of induced k-cycles which can be contained in an n-vertex graph which can be embedded in \(\varSigma \)?

The results of Huynh, Joret, and Wood [15] and Liu [17] described above extend to all surfaces \(\varSigma \). Combined, these results show that the answer to Question 1 is \(\varTheta (n^{\left\lfloor { k/2 }\right\rfloor })\) for all \(k\ge 3\) and all surfaces \(\varSigma \).

Note added. At a similar time to when this paper was first made available, the authors of [7] updated their paper and independently proved Theorem 2 (see [8]). Also, since the original release of this paper Lv, Győri, He, Salia, Tompkins, and Zhu [18] have published a preprint building on Cox and Martin’s work in [3] and [4] to prove their conjecture that \(f(n,C_{2k})=\left( \frac{n}{k}\right) ^k+o(n^k)\) for all \(k\ge 3\).

1.1 Notation and Organisation of the Paper

In this paper all graphs are simple, and we use the following standard graph theoretic notation and terminology. For a graph G we write V(G) and E(G) for the vertex and edge sets of G respectively. For a vertex v of a graph G we write \(N_G(v)\) for the set of neighbours of v in G, also called the neighbourhood of v in G, and \(d_G(v)\) for the degree of v in G. In both cases we drop the subscript if the graph in question is clear. For a graph G and a set \(S\subseteq V(G)\), we write G[S] for the induced subgraph of G with vertex set S, and \(G-S\) for the induced subgraph with vertex set \(V(G){\setminus } S\). We write \(K_{a,b}\) for the complete bipartite graph with parts of size a and b, and we write \(C_k\) for the k-cycle graph. For a planar graph G, by a drawing of G we mean a planar embedding of G. We sometimes use the phrase draw G to mean fix a drawing of G.

In Sect. 2 we prove Theorem 1 after stating and proving two preliminary lemmas. Section 3 contains the proof of Theorem 2, which is broken down into three small preliminary lemmas and two larger lemmas which are proved in Sects. 4 and 5 respectively. The proofs of these two lemmas contain the bulk of the work in proving the theorem. One of these proofs involves some repetitive case checking, which is handled in Appendix A.

In this section we give two preliminary lemmas and then prove Theorem 1.

Lemma 1

Let \(n\ge 4\) and suppose that G is an n-vertex planar graph in which every vertex of G is in at least \(n-3\) induced 4-cycles. If G contains a vertex of degree 2, then G is isomorphic to \(K_{2,n-2}\).

Proof

Suppose that \(v\in V(G)\) has degree 2. Let the neighbours of v be u and w. Since v is in at least \(n-3\) induced 4-cycles, the remaining \(n-3\) vertices of G are all adjacent to both u and w, so u and w are adjacent to all vertices of G except each other.

Suppose that \(x_1x_2x_3x_4\) is a 4-cycle in G which doesn’t contain u or w. Then \(\{u,x_1,x_3\}\) and \(\{w,x_2,x_4\}\) form the partite sets of a subdivision of \(K_{3,3}\) in G, which contradicts the planarity of G by Kuratowski’s theorem. Hence every 4-cycle in G contains u or w. Any induced 4-cycle in G containing u must also contain w, and vice versa, since no vertex in an induced 4-cycle can be a neighbour of all the others in the cycle. Hence every induced 4-cycle in G has the form uxwy for some \(x,y\in V(G){\setminus }\{u,w\}\).

Let \(z\in V(G){\setminus }\{u,w\}\). Then every induced 4-cycle in G containing z is of the form uzwy where \(y\in V(G){\setminus }\{u,w,z\}\). By assumption, there are at least \(n-3\) such cycles, so z is not adjacent to any vertex in G other than u and w. Therefore G is isomorphic to \(K_{2,n-2}\) as required. \(\square \)

Lemma 2

Let n be large, and suppose that G is an n-vertex planar graph in which every vertex of G is in at least \(n-3\) induced 4-cycles. Then G contains no vertices of degree 3, 4, or 5.

Proof

Suppose for a contradiction that \(v\in V(G)\) has degree 3, 4, or 5. Let the neighbours of v in G be \(x_1,\dots ,x_{d(v)}\). The number of induced 4-cycles in G containing v is at most

For each set of three neighbours of v, there is at most one common neighbour of all three other than v, otherwise G has an obvious \(K_{3,3}\) subgraph. So for each distinct pair of terms in (1), of which there are at most

there is at most one vertex contributing to both terms, i.e. there are at most 45 vertices which contribute to more than one term in the sum. Each of these could contribute up to 10 in total, since there are at most 10 terms in the sum, so the total contribution to the sum from these vertices is at most 450.

By assumption v is in at least \(n-3\) induced 4-cycles, so there are at least \(n-453\) induced 4-cycles containing v in which the vertex opposite v in the cycle is not in any other induced 4-cycle containing v. This implies that there are at least \(n-453\) vertices in \(V(G){\setminus }(\{v\}\cup N(v))\) which are adjacent to at least two neighbours of v. So there are at most 449 vertices in \(V(G){\setminus }(\{v\}\cup N(v))\) which are not adjacent to at least two neighbours of v.

By the pigeonhole principle, we may assume that

Draw G and consider the induced drawing of the complete bipartite graph with parts \(\{x_1,x_2\}\) and \((N(x_1)\cap N(x_2)){\setminus }( \{v\}\cup N(v))\). Label the vertices in the latter set as \(y_1,\dots ,y_k\) in natural order, where \(k\ge (n-3)/10\). The drawing of the complete bipartite graph splits the plane into k regions \(R_1,\dots ,R_k\), where for each i, \(R_i\) is bounded by the cycle \(x_1y_ix_2y_{i+1}\), where here and henceforth we take subscript addition to be modulo k.

Let \(R_j\) be the region with v in its interior. Then every vertex in N(v) is in \(R_j\) (including its boundary). Hence every vertex with a neighbour in \(N(v){\setminus }\{x_1,x_2\}\) is in \(R_{j-1}\cup R_j\cup R_{j+1}\) (including its boundary). There are at most 449 vertices in \(V(G){\setminus }(\{v\}\cup N(v))\) which are not adjacent to at least two neighbours of v, so there are at most 449 values of i other than \(j-1\), j, and \(j+1\) for which the interior of \(R_i\) contains a vertex of G. Thus, since n is large, there exists i such that \(R_{i-1}\) and \(R_i\) have no vertices in their interiors.

By assumption \(y_i\) is in at least \(n-3\) induced 4-cycles. Since

every such 4-cycle either contains the path \(y_{i-1}y_iy_{i+1}\) or the path \(x_1y_ix_2\). However since n is large (so \(k\ge 5\)), the existence of \(y_{i-2}\) and \(y_{i+2}\) implies there is no common neighbour of \(y_{i-1}\) and \(y_{i+1}\) in G other than \(x_1\) and \(x_2\), which are both also neighbours of \(y_i\). Hence there are no induced 4-cycles containing the path \(y_{i-1}y_iy_{i+1}\). Therefore there are \(n-3\) common neighbours of \(x_1\) and \(x_2\) besides \(y_i\), and \(y_i\) is not adjacent to any of them. Hence \(y_i\) has degree 2 in G, so by Lemma 1G is isomorphic to \(K_{2,n-2}\). But for large n this has no vertex of degree 3, 4, or 5, which gives the required contradiction and completes the proof of the lemma. \(\square \)

Proof of Theorem 1

First, it is straightforward to see that every induced 4-cycle in \(K_{2,n-2}\) contains exactly two vertices from the part of size \(n-2\), and that there is a unique, distinct induced 4-cycle containing each such pair, so the number of induced 4-cycles in \(K_{2,n-2}\) is \(\left( {\begin{array}{c}n-2\\ 2\end{array}}\right) =\frac{1}{2}(n^2-5n+6)\).

By Lemmas 1 and 2, to prove the theorem it is sufficient to show that for large n any n-vertex planar graph containing \(f_I(n,C_4)\) induced 4-cycles has no vertex in fewer than \(n-3\) induced 4-cycles. Indeed, if this is the case, then if n is large and G is an n-vertex planar graph containing \(f_I(n,C_4)\) induced 4-cycles, then the minimum degree of G is at most 5 by the planarity of G and at least 2 since every vertex is in at least one induced 4-cycle. So by the lemmas G is isomorphic \(K_{2,n-2}\).

Let n be large and suppose that G is an n-vertex planar graph in which every vertex of G is in more than \(n-3\) induced 4-cycles. Then as above the minimum degree of G is at least 2 but at most 5, so by Lemmas 1 and 2G is isomorphic to \(K_{2,n-2}\). But this contains vertices in at most \(n-3\) induced 4-cycles, which is a contradiction. Thus for large n, every n-vertex planar graph has a vertex in at most \(n-3\) induced 4-cycles.

For large n, deleting a vertex in at most \(n-3\) induced 4-cycles from an n-vertex planar graph containing \(f_I(n,C_4)\) induced 4-cycles yields an \((n-1)\)-vertex planar graph containing at least \(f_I(n,C_4)-n+3\) induced 4-cycles. This shows that, for large n, we have \(f_I(n,C_4)\le f_I(n-1,C_4)+n-3\).

We have seen that there are exactly \(\frac{1}{2}(n^2-5n+6)\) induced 4-cycles in \(K_{2,n-2}\) for each n, so there are \(n-3\) more induced 4-cycles in \(K_{2,n-2}\) than there are in \(K_{2,n-3}\). If \(f_I(n,C_4)< f_I(n-1,C_4)+n-3\) for infinitely many values of n, then for large enough n we have \(\frac{1}{2}(n^2-5n+6) > f_I(n,C_4)\), which is a contradiction. Hence for large n, \(f_I(n,C_4)=f_I(n-1,C_4)+n-3\). Therefore if n is large enough that this holds, and G is an n-vertex planar graph containing \(f_I(n,C_4)\) induced 4-cycles but also containing a vertex in fewer than \(n-3\) induced 4-cycles, then we can delete this vertex to obtain an \((n-1)\)-vertex planar graph containing more than \(f_I(n-1,C_4)\) induced 4-cycles, which is a contradiction. This completes the proof of the theorem. \(\square \)

3.1 Preliminaries to the Proof of Theorem 2

We start with the following definition.

Definition 2

Two vertices in a graph G are principal neighbours if they are adjacent and there is an induced 5-cycle in G containing both of them.

We will use the following notation and result adapted from [7]. Let v be a vertex of a planar graph G with distinct neighbours u and w. Let \(X^0_{uvw}=N(u){\setminus }(N(w)\cup \{w\})\) and let \(Y^0_{uvw}=N(w){\setminus }(N(u)\cup \{u\})\). Then let \(X_{uvw}\) be the set of vertices in \(X^0_{uvw}\) which have a neighbour in \(Y^0_{uvw}\), and similarly let \(Y_{uvw}\) be the set of vertices in \(Y^0_{uvw}\) which have a neighbour in \(X^0_{uvw}\). The following important lemma is a small adaptation of Lemma 1 in [7]. We include the proof here since it is short, provides intuition, and illustrates a method we will use repeatedly.

Lemma 3

([7]) Let G be a planar graph with \(v\in V(G)\) and \(u,w\in N(v)\) such that \(u\ne w\). Suppose that there is an induced 5-cycle in G containing the path uvw. Define the sets \(X_{uvw}\) and \(Y_{uvw}\) as above. Then \(G'\), the bipartite subgraph of G with vertex bipartition \(X_{uvw}\) and \(Y_{uvw}\), is a non-empty forest. Moreover the number of induced 5-cycles in G containing the path uvw is at most \(|E(G')|\), so in particular, there are at most \(|X_{uvw}|+|Y_{uvw}|-1\) such cycles.

Proof

Certainly any induced 5-cycle containing the path uvw contains an edge of \(G'\), and each of these edges is in at most one such cycle. Since there is an induced 5-cycle in G containing the path uvw, the graph \(G'\) is non-empty. Hence it is enough to show that \(G'\) is acyclic. Indeed, suppose \(G'\) contains a cycle \(x_1y_1x_2\dots x_ky_k\) for some \(k\ge 2\), \(x_i\in X_{uvw}\), and \(y_i\in Y_{uvw}\). Then G contains a subdivision of \(K_{3,3}\) with vertex classes \(\{u,y_1,y_2\}\) and \(\{w,x_1,x_2\}\) which is impossible since G is planar. \(\square \)

Our second preliminary lemma says that every drawing of a principal graph of the required form has a particular structure.

Lemma 4

Let \(n\ge 19\), and let G be an n-vertex principal graph of the required form. Given a drawing of G and a labelling of the vertices of G consistent with Definition 1, we may assume that the boundaries of the faces in the drawing consist of a fixed set of cycles, namely \(u_1u_2u_3\), \(u_1a_iwa_{i+1}\) for \(1\le i\le |A|-1\), \(u_2b_iwb_{i+1}\) for \(1\le i\le |B|-1\), \(u_3c_iwc_{i+1}\) for \(1\le i\le |C|-1\), \(u_1a_{|A|}wz_2\), \(u_1z_1z_2\), \(z_1z_2z_3\), \(z_2z_3w\), \(u_1u_2z_1\), \(u_2z_1z_4\), \(z_1z_3z_4\), \(z_3z_4w\), \(u_2z_4wb_1\), \(u_2b_{|B|}wz_5\), \(u_3z_5wc_1\), \(u_2u_3z_5\), \(u_3c_{|C|}wz_6\), \(u_1z_6wa_1\), and \(u_1u_3z_6\).

Proof

Consider the drawing of \(G - Z\) induced by the drawing of G. It is straightforward to see that we can relabel the vertices within each of A, B, and C such the faces of this drawing are bounded by the cycles \(u_1u_2u_3\), \(u_1a_iwa_{i+1}\) for \(1\le i\le |A|-1\), \(u_2b_iwb_{i+1}\) for \(1\le i\le |B|-1\), \(u_3c_iwc_{i+1}\) for \(1\le i\le |C|-1\), \(u_1a_{|A|}wb_1u_2\), \(u_2b_{|B|}wc_1u_3\), and \(u_3c_{|C|}wa_1u_1\).

It is clear which of these faces contains each of the vertices in Z in the drawing of G. One by one, add the vertices in Z (and their edges to the current graph) back to the drawing of \(G- Z\) in the order \(z_1,\dots ,z_6\), keeping track of the faces of the drawing and their boundaries at each step. At each step there is a unique face to which the next vertex can be added, and the cycles forming the boundaries of the faces in the resulting drawing are fixed. After adding \(z_6\), the cycles forming the boundaries of the faces are those in the list in the statement of the lemma. Clearly this new labeling of the vertices is still consistent with Definition 1. \(\square \)

Finally, we count the induced 5-cycles in a principal graph of the required form.

Lemma 5

Let \(n\ge 19\). Every principal n-vertex graph of the required form contains exactly \(\frac{1}{3}(n^2-8n+22)\) induced 5-cycles if \(n\equiv 1\pmod {3}\), and exactly \(\frac{1}{3}(n^2-8n+21)\) otherwise. Moreover, every n-vertex graph of the required form contains at least as many induced 5-cycles as a principal n-vertex graph of the required form.

Proof

Let G be a principal n-vertex graph of the required form, and label its vertices as in Definition 1. Let \(a\in A\), then the only neighbours of a are \(u_1\) and w. Define \(X=X_{u_1aw}\) and \(Y=Y_{u_1aw}\) as above, then the number of induced 5-cycles in G containing a is equal to the number of edges between these two sets. We see that \(X=\{u_2,u_3,z_1\}\) and \(Y=B\cup C\cup \{z_3,z_4,z_5\}\), and the number of edges between these sets is \(|B|+|C|+5\). None of these 5-cycles contain another vertex in A, so there are \(|A|(|B|+|C|+5)\) induced 5-cycles containing a vertex in A.

Now consider \(G-A\). By the same method, we see that each vertex in B is in \(|C|+5\) induced 5-cycles in \(G-A\), and none of these use another vertex in B, so there are \(|B|(|C|+5)\) induced 5-cycles in \(G-A\) containing a vertex in B. Applying the method once more to the graph \(G-(A\cup B)\) and a vertex in C, we find that there are 2|C| induced 5-cycles in that graph containing a vertex in C.

It remains to count the number of induced 5-cycles in \(G[\{u_1,u_2,u_3,w\}\cup Z]\). Let \(\varGamma \) be an induced 5-cycle in this graph and suppose that it does not contain w. Then the only available neighbours of \(z_5\) and \(z_6\) are \(u_2\) and \(u_3\), and \(u_1\) and \(u_3\) respectively, but both these pairs are adjacent, so neither \(z_5\) nor \(z_6\) are in \(\varGamma \). Then similarly \(u_3\) is not in \(\varGamma \). Now \(z_1\) is adjacent to all the remaining vertices, so it too is not in \(\varGamma \). Thus \(\varGamma \) is the induced 5-cycle \(u_1z_2z_3z_4u_2\).

Now suppose \(\varGamma \) contains w and \(z_5\). There are exactly five such cycles (two containing the path \(wz_5u_2u_1\), two containing \(wz_5u_2z_1\), one containing \(wz_5u_3u_1\), and none containing any other path of length 4 extending \(wz_5\) beyond \(z_5\)). By a similar count, there are exactly four induced 5-cycles containing w and \(z_6\) but not \(z_5\). If \(\varGamma \) contains w but not \(z_5\) or \(z_6\), then it must contain \(z_2\) and \(z_4\), and we see the only such cycle is \(u_1z_2wz_4u_2\).

So in total there are exactly \(|A||B|+|A||C|+|B||C|+5(|A|+|B|)+2|C|+11\) induced 5-cycles in G, which is \(\frac{1}{3}(n^2-8n+22)\) if \(n\equiv 1\pmod {3}\) and \(\frac{1}{3}(n^2-8n+21)\) otherwise. Finally, we see from this count that no induced 5-cycle in a principal graph of the required form contains two vertices which are the endpoints of an optional edge. Hence every n-vertex graph of the required form contains at least as many induced 5-cycles as the principal n-vertex graph of the required form that it contains. \(\square \)

3.2 Two Key Lemmas in the Proof of Theorem 2

The following two lemmas are the two key steps in the proof of Theorem 2.

Lemma 6

Let n be large, and suppose that G is an n-vertex planar graph containing \(f_I(n,C_5)\) induced 5-cycles. Suppose also that every vertex of G is in at least \(\left\lfloor { \frac{2(n-1)}{3} }\right\rfloor -2\) induced 5-cycles. Then it contains distinct vertices \(u_1\), \(u_2\), \(u_3\), a, b, c, and w, such that

1. 1.

   \(u_1\), \(u_2\), and \(u_3\) are all adjacent to one another but none are adjacent to w, and

2. 2.

   the principal neighbours of a, b, and c are exactly \(u_1\) and w, \(u_2\) and w, and \(u_3\) and w respectively.

Lemma 7

Let \(n\ge 19\), and suppose that G is an n-vertex planar graph containing \(f_I(n,C_5)\) induced 5-cycles. Suppose also that it contains distinct vertices \(u_1\), \(u_2\), \(u_3\), a, b, c, and w satisfying the conditions in Lemma 6. Then there exists a vertex of G in at most \(\left\lfloor { \frac{2(n-1)}{3} }\right\rfloor -2\) induced 5-cycles. If moreover \(n\equiv 1\pmod {3}\) and every vertex of G is in at least \(\left\lfloor { \frac{2(n-1)}{3} }\right\rfloor -2=\frac{2n-8}{3}\) induced 5-cycles, then G is of the required form and contains exactly \(\frac{1}{3}(n^2-8n+22)\) induced 5-cycles.

3.3 Proof of Theorem 2 Given the Key Lemmas

Before proving Lemmas 6 and 7 we use them to prove Theorem 2.

Proof of Theorem 2

Let n be large, and let G be an n-vertex planar graph containing \(f_I(n,C_5)\) induced 5-cycles. By Lemmas 6 and 7, some vertex of G is in at most \(\left\lfloor { \frac{2(n-1)}{3} }\right\rfloor -2\) induced 5-cycles. By deleting such a vertex from G we find that, for large n, \(f_I(n,C_5)\le f_I(n-1,C_5)+\left\lfloor { \frac{2(n-1)}{3} }\right\rfloor -2\).

Let c(n) denote the number of induced 5-cycles in an n-vertex principal graph of the required form. By Lemma 5 this is well-defined and satisfies \(c(n)=c(n-1)+\left\lfloor { \frac{2(n-1)}{3} }\right\rfloor -2\) for all \(n\ge 20\). Suppose that the inequality at the end of the last paragraph is strict for infinitely many values of n. Then for large enough n, we have \(c(n)> f_I(n,C_5)\) which is a contradiction since graphs of the required form are planar. Hence for large n, \(f_I(n,C_5) = f_I(n-1,C_5)+\left\lfloor { \frac{2(n-1)}{3} }\right\rfloor -2\).

Therefore, for large n, if G is an n-vertex planar graph containing \(f_I(n,C_5)\) induced 5-cycles, then every vertex of G is in at least \(\left\lfloor { \frac{2(n-1)}{3} }\right\rfloor -2\) induced 5-cycles, otherwise we could delete the vertex in the fewest induced 5-cycles to obtain an \((n-1)\)-vertex planar graph containing more than \(f_I(n-1,C_5)\) induced 5-cycles. Hence by Lemmas 6 and 7, if n is large with \(n\equiv 1\pmod {3}\), and G is an n-vertex planar graph containing \(f_I(n,C_5)\) induced 5-cycles, then G is of the required form. Moreover, for such n we have \(f_I(n,C_5)=\frac{1}{3}(n^2-8n+22)\). Hence for large n with \(n\equiv 0,2 \pmod {3}\) we have \(f_I(n,C_5)=\frac{1}{3}(n^2-8n+21)\), and so by Lemma 5, for large enough n every n-vertex graph of the required form contains \(f_I(n,C_5)\) induced 5-cycles. To complete the proof of the theorem it is sufficient to show that if n is large with \(n\equiv 0,2 \pmod {3}\), and G is an n-vertex planar graph containing \(f_I(n,C_5)\) induced 5-cycles, then G is of the required form.

Claim 1

Let n be large, with \(n\equiv 0\pmod {3}\) or \(n\equiv 2\pmod {3}\), and let G be an n-vertex planar graph containing \(f_I(n,C_5)\) induced 5-cycles. Suppose that G contains an \((n-1)\)-vertex graph of the required form, H, as an induced subgraph. Then G is of the required form.

Proof

Let v be the vertex we delete from G to obtain H. Let \(H_0\) be a principal graph of the required form on \(n-1\) vertices contained in H. Fix a drawing of G and consider the induced drawings of H and \(H_0\). By Lemma 4 we can label the vertices of H according to Definition 1 such that the boundaries of the faces in the drawing of \(H_0\) consist of the cycles listed in that lemma.

The only non-triangular faces in the drawing of H have a boundary consisting of a cycle from the list in Lemma 4 of the form \(u_iywy'\) for some \(i\in \{1,2,3\}\) and \(y,y'\in A\cup B\cup C\cup Z\). We know that v is contained in at least \(\left\lfloor { \frac{2(n-1)}{3} }\right\rfloor -2\) induced 5-cycles in G so it cannot be contained in a triangular face of H. Let the face of H which contains v be bounded by cycle \(u_iywy'\), with i, y, and \(y'\) as above. Both y and \(y'\) have degree at most 5 in H so by Lemma 3, since n is large, these cannot be the only principal neighbours of v in G. Hence v is adjacent to \(u_i\) and w. Its only other possible neighbours are y and \(y'\), so by the planarity of G it is now clear that if \(n\equiv 2\pmod {3}\), then G is of the required form.

If \(n\equiv 0\pmod {3}\), then there is some \(i\in \{1,2,3\}\) for which this does not imply that G is of the required form. If \(n\equiv 0\pmod {3}\), then by the proof of Lemma 5, one of the vertex classes A, B, and C in H is such that all the vertices in that class are in exactly \(\left\lfloor { \frac{2(n-2)}{3} }\right\rfloor -2=\frac{2n}{3}-4\) induced 5-cycles in H. This is strictly less than \(\left\lfloor { \frac{2(n-1)}{3} }\right\rfloor -2=\frac{2n}{3}-3\) and hence each vertex in that class must be in an induced 5-cycle containing v in G. Suppose that A is the class to which this applies (similar arguments hold for B and C). Then it is enough to show that \(i\ne 1\) in the argument above.

Suppose for a contradiction that v is adjacent to \(u_1\) and w in G. Vertex \(a_3\) is in an induced 5-cycle containing v in G, and this 5-cycle cannot contain both \(u_1\) and w, so there is a path of length at most 3 from \(a_3\) to v which avoids \(u_1\) and w. Using the list of cycles forming the boundaries of the faces in the drawing of \(H_0\), we can deduce that the only vertices to which there is a path in H of length at most 2 which avoids \(u_1\) and w are \(a_1\), \(a_2\), \(a_3\), \(a_4\), and \(a_5\). Thus v is adjacent to one of these five vertices in G. Similarly, since \(a_9\) is an induced 5-cycle containing v in G, v is adjacent to one of \(a_7\), \(a_8\), \(a_9\), \(a_{10}\), and \(a_{11}\). However using the list of the boundaries of the faces in the drawing of \(H_0\) again, we see that this is impossible. Hence \(i\ne 1\) as required, and if \(n\equiv 0\pmod {3}\), then G is of the required form. \(\square \)

To conclude, let n be large with \(n\equiv 2\pmod {3}\), and let G be an n-vertex planar graph containing \(f_I(n,C_5)\) induced 5-cycles. Then there is a vertex in exactly \(\left\lfloor { \frac{2(n-1)}{3} }\right\rfloor - 2\) induced 5-cycles in G, and deleting this vertex gives an \((n-1)\)-vertex planar graph containing \(f_I(n-1,C_5)\) induced 5-cycles. Since \(n-1\equiv 1\pmod {3}\), this graph is of the required form. Hence by the claim, G is of the required form. Repeating this argument, we can extend this to \(n\equiv 0 \pmod {3}\). This completes the proof of the theorem. \(\square \)

Following the authors of [7], we say that in a drawing of a planar graph G, an empty \(K_{2,7}\) is a \(K_{2,7}\) subgraph of G with parts \(\{a_1,a_2\}\) and \(\{b_1,\dots ,b_7\}\), with \(b_1,\dots ,b_7\) labelled in a natural order in the drawing, such that in the drawing of G the bounded region with boundary \(a_1b_1a_2b_7\) contains exactly the vertices \(b_2,\dots ,b_6\). Empty \(K_{2,7}\)’s will be useful in the proof of Lemma 6 since, with notation as above, \(a_1\) and \(a_2\) are the only principal neighbours of \(b_4\) in the graph. Indeed, the only other possible neighbours of \(b_4\) are \(b_3\) and \(b_5\), but there is no path of length 3 from \(b_3\) to \(b_5\) avoiding \(a_1\), \(a_2\), and \(b_4\), so no induced 5-cycle contains the path \(b_3b_4b_5\). Also, no induced 5-cycle contains the path \(a_ib_4b_j\) for \(i\in \{1,2\}\) and \(j\in \{3,5\}\) since \(a_i\) and \(b_j\) are neighbours. Similarly, \(a_1\) and \(a_2\) are the only principal neighbours of \(b_2\), \(b_3\), \(b_5\), and \(b_6\).

The proof of Lemma 6 will use the following three results, proved in [7] as Lemma 2, Lemma 4, and Corollary 1 respectively.^{Footnote 1}

Lemma 8

([7]) Let n be large and let G be an n-vertex plane graph in which every vertex is in more than \(\frac{11n}{20}\) induced 5-cycles. Then G contains an empty \(K_{2,7}\).

Lemma 9

([7]) Let n be large and let G be an n-vertex plane graph in which every vertex is in more than \(\frac{11n}{20}\) induced 5-cycles. Let u and w be distinct vertices of G, and let \(v_1,\dots ,v_6\) be some of their common neighbours, labelled in a natural order in the drawing of G. Suppose that the interior of the bounded region with boundary formed of the cycle \(uv_3wv_4\) contains no common neighbours of u and w. Then if this region contains a vertex, then it contains at least \(n^{1/5}\) vertices.

Lemma 10

([7]) Let n be large and let G be an n-vertex plane graph in which every vertex is in more than \(\frac{11n}{20}\) induced 5-cycles. If u and w are distinct vertices of G with \(|N(u)\cap N(w)|\ge 7n^{4/5}\), then G contains an empty \(K_{2,7}\) whose part of size 2 is \(\{u,w\}\).

We now prove Lemma 6. The proof is a very slight adaptation of that of Lemmas 5 and 6 from [7], but we repeat it here for completeness.

Proof of Lemma 6

Fix a drawing of G. By Lemma 8 this drawing contains an empty \(K_{2,7}\). Let u and w be the vertices in the part of size 2, and let v be the ‘central’ vertex of the seven in the other part. Then u and w are the only principal neighbours of v, so in particular u and w are not adjacent. Let \(X=X_{uvw}\) and \(Y=Y_{uvw}\) be defined as in Sect. 3.1. Then by Lemma 3 we have \(|X|+|Y|\ge \left\lfloor { \frac{2(n-1)}{3} }\right\rfloor -1\). Let \(G'\) be the induced bipartite graph between X and Y.

Claim 2

No vertex in \(V(G){\setminus }(Y\cup \{u\})\) is adjacent to more than two vertices in X, and no vertex in \(V(G){\setminus }(X\cup \{w\})\) is adjacent to more than two vertices in Y.

Proof

Suppose for a contradiction that \(a\in V(G){\setminus }(Y\cup \{u\})\) is adjacent to three vertices in X, say \(x_1\), \(x_2\), and \(x_3\). By the definition of X, \(a\ne w\) and \(x_1,x_2,x_3\in N(u)\). Moreover, there is a path of length 2 to each of \(x_1\), \(x_2\), and \(x_3\) from w, where the middle vertex in the path is in Y. Hence there exists a vertex \(b\in Y\cup \{w\}\) such that G contains a subdivision of \(K_{3,3}\) with parts \(\{x_1,x_2,x_3\}\) and \(\{u,a,b\}\), contradicting Kuratowski’s theorem. This proves the first statement, and the second is similar. \(\square \)

Claim 3

The maximum degree of \(G'\) is at least \(n^{5/6}\).

Proof

Suppose otherwise. We will start by showing that u and w have a common neighbourhood of size at least \(\frac{1}{3}n+o(n)\). Let \(x\in X\). By assumption, x is in at least \(\left\lfloor { \frac{2(n-1)}{3} }\right\rfloor -2\) induced 5-cycles in G. If an induced 5-cycle contains u, x, and w, then since neither u nor x is adjacent to w, and by the definition of Y, the 5-cycle must be of the form uxywa for some \(y\in Y\) and \(a\in N(u)\cap N(w)\). Hence the number of such 5-cycles is at most \(d_{G'}(x)|N(u)\cap N(w)|\).

If an induced 5-cycle contains x but not both u and w, then each vertex in the cycle which is not adjacent to x is either w or has a path of length at most 3 to x which avoids both u and w. For a vertex \(z\in X\cup Y\), let T(z) be the number of vertices of G from which there is a path to z of length at most 3 which avoids both u and w. Then by Lemma 3 there are at most \(\left( {\begin{array}{c}d_G(x)\\ 2\end{array}}\right) T(x)\) induced 5-cycles in G containing x but not both u and w.

Similar arguments hold if we replace x with a vertex in Y, so for all \(z\in X\cup Y\) we have

To show that \(|N(u)\cap N(w)|\) is ‘large’ we will therefore aim to show that there exists \(z\in X\cup Y\) such that \(d_{G'}(z)\), \(d_G(z)\), and T(z) are ‘small’.

First, recall from the proof of Lemma 3 that \(G'\) is planar and hence has at most \(|X|+|Y|-1\) edges. So if \(l_1\) is the number of vertices of degree at least 3 in \(G'\), then \(3l_1\le 2(|X|+|Y|-1)\), which gives

Hence there are at least \(\frac{n}{5}\) vertices in \(G'\) with degree at most 2.

Next, since G is planar it has at most 3n edges. If \(l_2\) is the number of vertices of degree at least 61 in G, then \(61l_2\le 6n\), so \(l_2\le \frac{n}{10}\). Thus there are at least \(\frac{9n}{10}\) vertices in G with degree at most 60.

Finally we turn to T(z). Take a maximal matching in \(G'\) between X and Y. Label the vertices in this matching as \(x_1,\dots ,x_k\) and \(y_1,\dots ,y_k\) where \(x_i\in X\) and \(y_i\in Y\) for all i, where edge \(x_iy_i\) is in the matching for all i, and where the vertices \(x_1,\dots ,x_k\) are arranged in that order around u in the drawing of G. This matching, along with the edges \(ux_i\) and \(wy_i\) for each i split the plane into k regions \(R_1,\dots ,R_k\), where \(R_i\) has boundary \(ux_iy_iwy_{i+1}x_{i+1}\) for each i, with the addition in the subscripts taken modulo k. Since the matching is maximal, every vertex in \(X\cup Y\) in the interior of region \(R_i\) is adjacent to one of the vertices in \(X\cup Y\) on its boundary. We have assumed that the maximum degree of \(G'\) is less than \(n^{5/6}\), so the total number of vertices in \(X\cup Y\) in each region \(R_i\) (including the vertices on its boundary) is at most \(4n^{5/6}\).

Let q be any vertex of G which is not u or w. Then there is some \(1\le i\le k\) such that q is in \(R_i\) (including possibly on its boundary). If z is a vertex in \(X\cup Y\) such that there is a path in G of length at most 3 from q to z avoiding u and w, then z is in \(R_{i-4}\cup \dots \cup R_{i+4}\) (including on its boundary) where again the addition in the subscripts is modulo k. Hence there are at most \(36n^{5/6}\) vertices z for which this can hold, and at most \(36n^{11/6}\) pairs (q, z) for which this holds. Let \(l_3\) be the number of vertices in \(X\cup Y\) with \(T(z)\ge 1000n^{5/6}\). Then there are at least \(1000l_3n^{5/6}\) pairs (q, z) as above, so \(1000l_3n^{5/6}\le 36n^{11/6}\). Rearranging, we find \(l_3\le \frac{36n}{1000}\le \frac{n}{20}\).

Combining these three calculations, there are at least \(\frac{n}{5}\) vertices \(z\in X\cup Y\) with \(d_{G'}(z)\le 2\), of which at most \(\frac{n}{10}\) have degree greater than 60 in G and at most \(\frac{n}{20}\) have \(T(z)\ge 1000n^{5/6}\). So there exists \(z\in X\cup Y\) with \(d_{G'}(z)\le 2\), \(d_G(z)\le 60\), and \(T(z)<1000n^{5/6}\). Hence by (2) we have

To complete the proof of the claim we will show that G contains at most \(\frac{2}{9}n^2+o(n^2)\) induced 5-cycles. By Lemma 5, an n-vertex principal graph of the required form contains \(\frac{1}{3}n^2+O(n)\) induced 5-cycles, so since n is large this contradicts G containing \(f_I(n,C_5)\) induced 5-cycles.

Label the vertices in \(N(u)\cap N(w)\) in the order they’re arranged around u as \(v_1,\dots ,v_t\). The drawing of the bipartite graph with parts \(\{u,w\}\) and \(\{v_1,\dots ,v_t\}\) contained in the drawing of G splits the plane into t regions \(R_1,\dots ,R_t\), where \(R_i\) has boundary \(uv_iwv_{i+1}\), with the addition in the subscript taken modulo t. By Lemma 9, if any of the interiors of the regions \(R_3,\dots ,R_{t-3}\) contain a vertex, then they contain at least \(n^{1/5}\) vertices, so at most \(n^{4/5}\) of these interiors contain a vertex.

Thus for all but o(n) values of i, none of the regions \(R_{i-3}, R_{i-2}, \dots , R_{i+2}\) have any vertices in their interior, and hence the only principal neighbours of \(v_i\) are u and w. This implies that \(v_i\) is in at most \(|X|+|Y|-1\le n-|N(u)\cap N(w)|\le \frac{2}{3}n+o(n)\) induced 5-cycles in G. Hence deleting all \(\frac{1}{3}n+o(n)\) of these vertices \(v_i\) removes at most \(\frac{2}{9}n^2+o(n^2)\) induced 5-cycles.

Let H be the graph which remains after these vertices have been deleted. Then H contains \(\frac{2}{3}n+o(n)\) vertices, and it is enough to show that it contains \(o(n^2)\) induced 5-cycles. First, let \(S=V(H){\setminus }(X\cup Y\cup \{u,w\})\). Then since \(|X|+|Y|\ge \left\lfloor { \frac{2(n-1)}{3} }\right\rfloor -1\), S has size o(n). By Claim 2, no vertex in S is adjacent to more than six vertices in \(X\cup Y\cup \{u,w\}\). Since H[S] is planar, there is therefore a vertex in S of degree at most 11 in H. By Lemma 3 this vertex is in at most \(\left( {\begin{array}{c}11\\ 2\end{array}}\right) n\) induced 5-cycles in H. Hence removing the vertices in S from H one by one, at each stage removing the vertex with the smallest degree, we find that deleting S from H removes only \(o(n^2)\) induced 5-cycles.

It remains to show that \(H'=G[X\cup Y\cup \{u,w\}]\) contains only \(o(n^2)\) induced 5-cycles. Let \(\varGamma \) be an induced 5-cycle in \(H'\) and suppose it contains neither u nor w. If \(\varGamma \) contains a path that goes from X to Y, then back X, then back to Y, then in a similar way to in the proof of Lemma 3, this implies the existence of a subdivision of \(K_{3,3}\) in G. Hence, the subgraphs of \(\varGamma \) induced on \(V(\varGamma )\cap X\) and \(V(\varGamma )\cap Y\) each have at most one component. By Claim 2, given \(x\in V(\varGamma )\cap X\) there are only O(1) possibilities for \(V(\varGamma )\cap X\), and similarly for Y given \(y\in V(\varGamma )\cap Y\). Moreover, if \(\varGamma \) contains vertices both from X and from Y, then given \(V(\varGamma )\cap X\) there are \(O(n^{5/6})\) possibilities for \(V(\varGamma )\cap Y\), since by assumption an endpoint of the path induced on \(V(\varGamma )\cap X\) has fewer than \(n^{5/6}\) neighbours in Y, and given this neighbour there are O(1) possibilities for \(V(\varGamma )\cap Y\) by the above. Thus, given a vertex of \(\varGamma \), without loss of generality in X, there are O(1) options for \(V(\varGamma )\cap X\), then \(O(n^{5/6})\) options for \(V(\varGamma )\cap Y\). It follows that there are \(O(n^{11/6})=o(n^2)\) induced 5-cycles in \(H'\) which contain neither u nor v.

The final step in the proof of the claim will be to show that there are only \(o(n^2)\) induced 5-cycles in \(H'\) containing u or w. We do this by deleting the vertices in \(X\cup Y\) one by one in such an order that at each stage the vertex we delete is in o(n) induced 5-cycles containing u or w. The vertex we delete at each step is a vertex in what remains of \(X\cup Y\) which has the lowest degree in what remains of \(G'\). Since \(G'\) is a forest, this vertex has degree at most 1 in \(G'\).

Consider a particular step in the deletion process where without loss of generality we are deleting \(x\in X\). If \(\varGamma \) is an induced 5-cycle in \(H'\) containing x and one of u and w, then it must be of the form \(uxyy'x'\) or \(wyxx'y'\) for \(x'\in X\) and \(y,y'\in Y\). If x has degree 0 in what remains of \(G'\), then clearly there are no such cycles. Otherwise let y be the unique neighbour of x in what remains of Y. By Claim 2, y has at most two neighbours in Y, and by assumption each of these has at most \(n^{5/6}\) neighbours in X. Similarly, x has at most two neighbours in X and each of these has at most \(n^{5/6}\) neighbours in Y. Thus x is in o(n) induced 5-cycles containing u or w in the current graph, as required. \(\square \)

Relabel v and u as a and \(u_1\) respectively. By Claim 3, without loss of generality there is a vertex \(u_2\in X\) with at least \(n^{5/6}\) neighbours in Y. So the complete bipartite graph with parts \(\{u_2,w\}\) and \(N(u_2)\cap N(w)\) contains an empty \(K_{2,7}\) by Lemma 10. Let \(b_1\), \(b_2\), and \(b_3\) be the central three vertices of the part of size 7, then \(u_2\) and w are the only principal neighbours of each of these vertices. None of \(b_1\), \(b_2\), and \(b_3\) are equal to \(u_1\), since \(u_1\) and w are not neighbours, and moreover at most two of these vertices are adjacent to \(u_1\), otherwise G has a \(K_{3,3}\) subgraph. Let b be one of the three which is not adjacent to \(u_1\), then \(b\in Y\) by the definition of Y.

Let \(X'=X_{u_2bw}\) and \(Y'=Y_{u_2bw}\). Then by Lemma 3, \(|X'|+|Y'|\ge \left\lfloor { \frac{2(n-1)}{3} }\right\rfloor -1\), so \(|(X\cup Y)\cap (X'\cup Y')|\ge \frac{1}{4}n\). Clearly \(X\cap Y'\) and \(X'\cap Y\) are empty, so \(|X\cap X'|+|Y\cap Y'|\ge \frac{1}{4}n\). If \(z\in X\cap X'\), then z is a vertex in X which is adjacent to \(u_2\in X\), so \(|X\cap X'|\le 2\) by Claim 2. Thus \(|Y\cap Y'|\ge \frac{1}{5}n\).

Let \(z_1\), \(z_2\), and \(z_3\) be distinct vertices in \(Y\cap Y'\). Let \(t_1\), \(t_2\), and \(t_3\) be (not necessarily distinct) vertices in \(X'\) such that \(z_i\) and \(t_i\) are neighbours for each \(i=1,2,3\). Without loss of generality, the cycle \(u_2t_2z_2wb\) splits the plane into two regions, one of which contains \(z_1\) and the other of which contains \(z_3\). Again without loss of generality, \(u_1\) is in the same region as \(z_1\). Since \(z_3\in Y\), there is a path of length 2 from \(u_1\) to \(z_3\), so \(u_1\) and \(z_3\) have a common neighbour among the vertices in the cycle \(u_2t_2z_2wb\). However, \(u_2\not \in N(z_3)\) since \(z_3\in Y'\), \(z_2\not \in N(u_1)\) since \(z_2\in Y\), \(w\not \in N(u_1)\) since there is an induced 5-cycle in G containing the path \(u_1aw\), and \(b\not \in N(u_1)\) since \(b\in Y\). Hence \(t_2\in N(u_1)\), and consequently \(t_2\in X\).

Therefore all but at most two vertices in \(Y\cap Y'\) have a neighbour in \(X\cap X'\), but we know there are at most two vertices in \(X\cap X'\), so there exists one, say \(u_3\), with at least \(\frac{1}{12}n\) neighbours in \(Y\cap Y'\). Then \(u_3\) and w have a common neighbourhood of size at least \(\frac{1}{12}n\) in G, so by Lemma 10G contains an empty \(K_{2,7}\) whose part of size 2 is \(\{u_3,w\}\). Let c be the central vertex in the part of size 7. Since \(u_2\in X\) and \(u_3\in X\cap X'\), we have that \(u_1\), \(u_2\), and \(u_3\) are all mutually adjacent and none are adjacent to w. The principal neighbours of a, b, and c are exactly \(u_1\) and w, \(u_2\) and w, and \(u_3\) and w respectively, and thus the lemma is proved. \(\square \)

We now prove Lemma 7.

Proof of Lemma 7

As in the statement of the lemma, let \(n\ge 19\), and let G be an n-vertex planar graph containing \(f_I(n,C_5)\) induced 5-cycles. Suppose that G contains distinct vertices \(u_1\), \(u_2\), \(u_3\), a, b, c, and w satisfying the conditions in the statement of Lemma 6. Let A be the set of vertices of G whose principal neighbours are exactly \(u_1\) and w. Let B and C be the corresponding sets for \(u_2\) and w, and \(u_3\) and w respectively. Note that \(a\in A\), \(b\in B\), and \(c\in C\) but \(u_1,u_2,u_3,w\not \in A\cup B\cup C\).

Define H to be the graph obtained by deleting from G any edges with one endpoint in A and the other endpoint not in \(\{u_1,w\}\), and also any analogous edges for B and C. Then H is a planar n-vertex graph which, by the definitions of A, B, and C, has the same set of induced 5-cycles as G.

Let \(Z=V(H){\setminus }(A\cup B\cup C\cup \{u_1,u_2,u_3,w\})\). Then the graph \(H-Z\) consists of the triangle \(u_1u_2u_3\) and the three complete bipartite graphs with parts \(\{u_1,w\}\) and A, \(\{u_2,w\}\) and B, and \(\{u_3,w\}\) and C (see Fig. 3). It is straightforward to see that a is in exactly \(|B|+|C|\) induced 5-cycles in H which avoid Z, and analogously for b and c. In fact, we see that there are exactly \(|A||B|+|A||C|+|B||C|\) induced 5-cycles in H which avoid Z.

Let \(k_1\), \(k_2\), and \(k_3\) be the non-negative numbers such that a, b, and c are in exactly \(|B|+|C|+k_1\), \(|A|+|C|+k_2\), and \(|A|+|B|+k_3\) induced 5-cycles in H respectively. Let \(T=2(|A|+|B|+|C|)+k_1+k_2+k_3\) be the sum of these numbers. Since \(|A|+|B|+|C|=n-|Z|-4\), we have

Vertices a, b, and c are respectively in \(k_1\), \(k_2\), and \(k_3\) induced 5-cycles in H containing a vertex of Z. If an induced 5-cycle in H contains two vertices from a, b, and c, then it does not contain any vertices in Z, so the number of induced 5-cycles in H which contain a vertex in Z and one of a, b, and c is \(k_1+k_2+k_3\).

Using a similar approach to that used in the proof of Lemma 4, it is straightforward to see that for any drawing of \(H-Z\) there exists a labeling of the vertices of A as \(a_1,\dots ,a_{|A|}\) and similarly for B and C such that the faces of the drawing have boundaries given by the cycles \(u_1u_2u_3\), \(u_1a_{|A|}wb_1u_2\), \(u_2b_{|B|}wc_1u_3\), \(u_3c_{|C|}wa_1u_1\), \(u_1a_iwa_{i+1}\) for \(1\le i \le |A|-1\), \(u_2b_iwb_{i+1}\) for \(1\le i \le |B|-1\), and \(u_3c_iwc_{i+1}\) for \(1\le i \le |C|-1\). Fix a drawing of H, consider the induced drawing of \(H-Z\), and label the vertices of A, B, and C as above. We will refer to the faces whose boundaries are the second, third, and fourth of the cycles listed as \(F_1\), \(F_2\), and \(F_3\) respectively (see Fig. 3).

We now consider which faces of the drawing of \(H-Z\) contain vertices of Z in the drawing of H. Suppose \(|A|\ge 2\), and let \(Z_0\subseteq Z\) be the set of vertices in the face with boundary \(u_1a_1wa_2\). Then the only vertices in \(V(H){\setminus } Z_0\) which could be adjacent to a vertex in \(Z_0\) are \(u_1\) and w. The only neighbours of \(a_{|A|}\) in H are \(u_1\) and w, so we can redraw H with no vertices in the face with boundary \(u_1a_1wa_2\) by moving the vertices in \(Z_0\) into \(F_1\). Repeating this process for the other faces of \(H-Z\) whose boundaries are 4-cycles, we see that way may assume that all vertices of Z are in \(F_1\), \(F_2\), \(F_3\), or the triangular face.

If \(z\in Z\) is in an induced 5-cycle in H containing one of a, b, and c, then z is at distance 1 or 2 from w. Therefore z is not in the triangular face of \(H-Z\), so it is in one of \(F_1\), \(F_2\), or \(F_3\). Note that no induced 5-cycle in H containing one of a, b, and c can contain vertices in Z from two of \(F_1\), \(F_2\), and \(F_3\). Hence the number of induced 5-cycles in H containing one of a, b, and c and a vertex in Z is the sum over \(F_1\), \(F_2\), and \(F_3\) of the number of such cycles containing a vertex of Z in that face.

Let \(Z_1\subseteq Z\) be the set of vertices in \(F_1\). For each \(S\subseteq \{u_1,u_2,w\}\), let \(L_S\) be the set of vertices in \(Z_1\) whose neighbours among \(u_1\), \(u_2\), and w are exactly the vertices in S, and let \(l_S=|L_S|\). The number of induced 5-cycles containing c and a vertex in \(Z_1\) is \(2l_{\{u_1,u_2,w\}}+l_{\{u_1,w\}} +l_{\{u_2,w\}}\). The number of induced 5-cycles containing b and a vertex in \(Z_1\) is \(l_{\{u_1,w\}}\) plus the number of paths \(u_2z_1z_2w\) where \(z_1, z_2\in Z_1\) are such that \(z_1\not \in N(w)\) and \(z_2\not \in N(u_2)\). The number of such paths is the number of edges between \(L_{\{u_2\}}\cup L_{\{u_1,u_2\}}\) and \(L_{\{w\}}\cup L_{\{u_1,w\}}\). By a similar argument to that used in the proof of Lemma 3, the bipartite graph between these two sets is a forest. Moreover, it is straightforward to use the planarity of H to show that there can be at most one vertex in \(L_{\{u_1,w\}}\) which has a neighbour in \(L_{\{u_2\}}\cup L_{\{u_1,u_2\}}\).

Hence the number of paths \(u_2z_1z_2w\) is at most \(l_{\{u_2\}}+ l_{\{u_1,u_2\}} + l_{\{w\}}\), with equality only if one of the following holds:

1. (i)

   there is a vertex in \(L_{\{u_1,w\}}\) which has a neighbour in \(L_{\{u_2\}}\cup L_{\{u_1,u_2\}}\), every vertex in \(L_{\{u_1,u_2\}}\) has a neighbour in \(L_{\{w\}}\cup L_{\{u_1,w\}}\), and every vertex in \(L_{\{w\}}\) has a neighbour in \(L_{\{u_2\}}\cup L_{\{u_1,u_2\}}\), or

2. (ii)

   \(l_{\{u_2\}}=l_{\{u_1,u_2\}}=l_{\{w\}}=0\).

Indeed, if there is no vertex in \(L_{\{u_1,w\}}\) with a neighbour in \(L_{\{u_2\}}\cup L_{\{u_1,u_2\}}\), then since the bipartite graph between \(L_{\{u_2\}}\cup L_{\{u_1,u_2\}}\) and \(L_{\{w\}}\) is a forest it contains at most \(l_{\{u_2\}}+ l_{\{u_1,u_2\}} + l_{\{w\}}\) edges, with equality if and only if it has no vertices. If instead there is a vertex \(p\in L_{\{u_1,w\}}\) which has a neighbour in \(L_{\{u_2\}}\cup L_{\{u_1,u_2\}}\), then the number of edges in the bipartite graph between \(L_{\{u_2\}}\cup L_{\{u_1,u_2\}}\) and \(L_{\{w\}}\cup L_{\{u_1,w\}}\) is the same as the number of edges between \(L_{\{u_2\}}\cup L_{\{u_1,u_2\}}\) and \(L_{\{w\}}\cup \{p\}\). Again, this is at most \(l_{\{u_2\}}+ l_{\{u_1,u_2\}} + l_{\{w\}}\) with equality if and only if the forest is connected, which in particular implies that (i) is satisfied.

So the number of induced 5-cycles containing b and a vertex in \(Z_1\) is at most \(l_{\{u_1,w\}}+l_{\{u_2\}}+l_{\{u_1,u_2\}} + l_{\{w\}}\) with equality only if one of (i) or (ii) holds. We can similarly bound the number of induced 5-cycles containing a and a vertex in \(Z_1\) by swapping the roles of \(u_1\) and \(u_2\). Let the conditions corresponding to (i) and (ii) in this setting be called (i)\('\) and (ii)\('\). Summing, we find that the total number of induced 5-cycles that contain one of a, b, and c and a vertex in \(Z_1\) is at most \(2l_{\{u_1,u_2,w\}}+2l_{\{u_1,w\}} +2l_{\{u_2,w\}}+ l_{\{u_2\}}+ 2l_{\{u_1,u_2\}} + 2l_{\{w\}} + l_{\{u_1\}}\), with equality only if one of each of (i) and (ii), and (i)\('\) and (ii)\('\) hold.

Repeating for \(F_2\) and \(F_3\), and recalling that no vertices in the triangular face of \(H-Z\) are in an induced 5-cycle in H containing any of a, b, and c, we find that there are at most twice as many induced 5-cycles in H containing one of a, b, and c and a vertex in Z as there are vertices in Z. Recall that the number of such cycles is \(k_1+k_2+k_3\), which is equal to \(T-2n+2|Z|+8\) by (3). Hence

Suppose that all the vertices in G, so in particular a, b, and c, are in at least \(\left\lfloor { \frac{2(n-1)}{3} }\right\rfloor -1\) induced 5-cycles. Then this is also true in H, so

This is a contradiction, so there is a vertex of G in at most \(\left\lfloor { \frac{2(n-1)}{3} }\right\rfloor -2\) induced 5-cycles, which proves the first part of the lemma.

We now prove the second part of the lemma, so assume that \(n\equiv 1\pmod {3}\) and every vertex of G is in at least \(\left\lfloor { \frac{2(n-1)}{3} }\right\rfloor -2=\frac{2n-8}{3}\) induced 5-cycles. Then the same is true in H, so \(T\ge 2n-8\). So in fact we have \(T=2n-8\), and each of a, b, and c are in exactly \(\frac{2n-8}{3}\) induced 5-cycles. Moreover, the fact that we have equality in (4) implies that there are exactly twice as many induced 5-cycles in H containing one of a, b, and c and a vertex in Z as there are vertices in Z. Hence there are no vertices of Z in the triangular face of \(H-Z\), and in \(F_1\) we must have \(l_\emptyset =l_{\{u_2\}}=l_{\{u_1\}}=0\) and one of each of conditions (i) and (ii), and (i)\('\) and (ii)\('\) must hold (and analogously in \(F_2\) and \(F_3\)).

We now use these conditions on the vertices in \(Z_1\) to show that \(H[Z_1\cup \{u_1,u_2,w\}]\) must belong to one of three families of graphs. The same will hold for faces \(F_2\) and \(F_3\) by symmetry. The first possibility is that \(Z_1=\emptyset \), in which case we will say that \(F_1\) is of type 1. The second possibility is that \(Z_1\) contains a single vertex z which is adjacent to all of \(u_1\), \(u_2\), and w, in which case we will say that \(F_1\) is of type 2.

The final possibility is that \(Z_1\) contains \(m\ge 3\) vertices \(z_1,\dots ,z_m\) and \(H[Z_1\cup \{u_1,u_2,w\}]\) contains the edges \(u_1u_2\), \(u_1z_1\), \(u_2z_1\), \(u_1z_2\), and \(u_2z_m\), and the edges \(z_1z_i\) and \(z_iw\) for all \(2\le i\le m\). The remaining edges of \(H[Z_1\cup \{u_1,u_2,w\}]\) form a subset of \(\{z_iz_{i+1}:2\le i\le m-1\}\). In this case we say that \(F_1\) is of type 3. The three possibilities for \(F_1\) are illustrated in Fig. 4, where red lines indicate edges each of whose presence does not affect whether the face is of that type.

Claim 4

Face \(F_1\) is of type 1, 2, or 3. By symmetry, the same is true for \(F_2\) and \(F_3\).

Proof

We know that \(l_\emptyset =l_{\{u_2\}}=l_{\{u_1\}}=0\) and one of each of conditions (i) and (ii), and (i)\('\) and (ii)\('\) hold. First, if condition (ii) holds, then \(l_{\{u_1,u_2\}}=l_{\{w\}}=0\). So all vertices in \(Z_1\) are adjacent to exactly the vertices in one of \(\{u_1,w\}\), \(\{u_2,w\}\), and \(\{u_1,u_2,w\}\) among \(u_1\), \(u_2\), and w. In particular all the vertices are adjacent to w. Suppose there exists \(z\in L_{\{u_1,w\}}\). Then since z is not in A, there is some \(z'\in Z_1\) which is a principal neighbour of z.

Let \(\varGamma \) be an induced 5-cycle in H containing both z and \(z'\). Then \(\varGamma \) does not contain w since it is a common neighbour of z and \(z'\). If every vertex in \(\varGamma \) is in \(Z_1\), then all its vertices are adjacent to \(u_1\) or \(u_2\) so without loss of generality, some two non-adjacent vertices in \(\varGamma \), say \(p_1\) and \(p_2\), are both adjacent to \(u_1\). Let \(q_1\) and \(q_2\) be two other distinct non-adjacent vertices of \(\varGamma \). Then \(\{w,p_1,p_2\}\) and \(\{u_1,q_1,q_2\}\) form the partite sets of a subdivision of \(K_{3,3}\) in G, which is a contradiction.

Thus \(\varGamma \) must contain a vertex which is not in \(Z_1\), so without loss of generality it contains \(u_1\). If it doesn’t contain \(u_2\), then the rest of its vertices are in \(Z_1\), and the two which are not adjacent to \(u_1\), say \(p_1\) and \(p_2\), must be adjacent to \(u_2\). Let \(q_1\) and \(q_2\) be the other two vertices in \(\varGamma \). Then \(\{u_1,w,p_1\}\) and \(\{u_2,q_1,q_2\}\) form the partite sets of a subdivision of \(K_{3,3}\) in H, giving a contradiction. If \(\varGamma \) does contain \(u_2\), then since \(u_1\) and \(u_2\) are neighbours, the other three vertices in \(\varGamma \) are in \(Z_1\). One of these three must be adjacent to neither \(u_1\) nor \(u_2\), but no such vertex exists. Hence \(l_{\{u_1,w\}}=0\). Similarly \(l_{\{u_2,w\}}=0\). If \(l_{\{u_1,u_2,w\}}=0\) then \(F_1\) is of type 1. It is straightforward to use the planarity of H to show that \(l_{\{u_1,u_2,w\}}\le 1\), so if \(l_{\{u_1,u_2,w\}}\ne 0\), then \(F_1\) is of type 2.

If condition (ii) doesn’t hold, then neither does condition (ii)\('\), so conditions (i) and (i)\('\) both hold. In particular,

1. (a)

   there is a vertex in \(L_{\{u_1,w\}}\) which has a neighbour in \(L_{\{u_1,u_2\}}\),

2. (b)

   there is a vertex in \(L_{\{u_2,w\}}\) which has a neighbour in \(L_{\{u_1,u_2\}}\),

3. (c)

   every vertex in \(L_{\{u_1,u_2\}}\) has a neighbour in \(L_{\{w\}}\cup L_{\{u_1,w\}}\), and

4. (d)

   every vertex in \(L_{\{w\}}\) has a neighbour in \(L_{\{u_1,u_2\}}\).

Condition (a) implies that \(l_{\{u_1,u_2\}}\ge 1\), and it is straightforward to deduce from (c) and the planarity of H that \(l_{\{u_1,u_2\}}\le 1\). It is also straightforward to use (a) and the planarity of H to deduce that \(l_{\{u_1,u_2,w\}}=0\). It remains to determine \(l_{\{u_1,w\}}\), \(l_{\{u_2,w\}}\) and \(l_{\{w\}}\).

Let \(z_1\) be the unique vertex in \(L_{\{u_1,u_2\}}\) and let \(z_2\) be a vertex in \(L_{\{u_1,w\}}\) which is adjacent to \(z_1\). Let \(m=l_{\{w\}}+3\) and let \(z_m\) be a vertex in \(L_{\{u_2,w\}}\) which is adjacent to \(z_1\). Consider \(H[\{u_1,u_2,w,a_{|A|}, b_1,z_1,z_2,z_m\}]\) with the edge \(z_2z_m\) deleted if present, and the drawing of this induced by our drawing of H. Face \(F_1\) is split into six faces whose boundaries are the cycles in a fixed list. Let \(E_1\), \(E_2\), and \(E_3\) respectively be the faces whose boundaries are formed of the cycles \(u_1a_{|A|}wz_2\), \(u_2b_1wz_m\), and \(z_1z_2wz_m\) (see Fig. 5). Any vertices in \(L_{\{u_1,w\}}{\setminus }\{z_2\}\) must be in \(E_1\) and any vertices in \(L_{\{u_2,w\}}{\setminus }\{z_m\}\) must be in \(E_2\). By (d), every vertex in \(L_{\{w\}}\) is in \(E_3\).

Suppose there exists some \(z\in L_{\{u_1,w\}}{\setminus }\{z_2\}\). Then since \(z\not \in A\), z has a principal neighbour other than \(u_1\) and w, say \(z'\). Then \(z'\) is either \(z_2\) or is in the interior of \(E_1\), so in particular \(z'\in L_{\{u_1,w\}}\). Let \(\varGamma \) be an induced 5-cycle in G containing z and \(z'\). Then \(\varGamma \) does not contain \(u_1\) or w since these are common neighbours of z and \(z'\). Hence every vertex in \(\varGamma \) is either \(z_2\) or is in the interior of \(E_1\), so they are all adjacent to \(u_1\) and w. By an argument similar to that used in the proof of Lemma 3, this implies the existence of a subdivision of \(K_{3,3}\) in H, which is a contradiction. Therefore \(L_{\{u_1,w\}}=\{z_2\}\) and similarly \(L_{\{u_2,w\}}=\{z_m\}\).

Consider adding the vertices in \(L_{\{w\}}\) and their edges to w and \(z_1\) to the drawing of \(H[\{u_1,u_2,w,a_{|A|}, b_1,z_1,z_2,z_m\}]\). We see that we can label them as \(z_3,\dots ,z_{m-1}\) such that to preserve planarity the only other edges which could be present in \(F_1\) are of the form \(z_iz_{i+1}\) for \(2\le i\le m-1\). Hence \(F_1\) is of type 3. This completes the proof of the claim. \(\square \)

To summarise, we know that:

• there are exactly \(|A||B|+|A||C|+|B||C|\) induced 5-cycles in \(H-Z\),

• a, b, and c are in \(|B|+|C|\), \(|A|+|C|\), and \(|A|+|B|\) induced 5-cycles in \(H-Z\) respectively,

• each of a, b, and c is in exactly \(\frac{2n-8}{3}\) induced 5-cycles in H,

• every vertex of Z is in \(F_1\), \(F_2\), or \(F_3\),

• each of \(F_1\), \(F_2\), and \(F_3\) is of type 1, 2, or 3,

• there are no induced 5-cycles in H containing two vertices in \(A\cup B\cup C\) and a vertex in Z, and

• there are no induced 5-cycles in H containing one of a, b, and c and vertices in Z from two of \(F_1\), \(F_2\), and \(F_3\).

For each assignment of types 1, 2, and 3 to faces \(F_1\), \(F_2\), and \(F_3\) and for each \(x\in \{a,b,c\}\), we now count how many induced 5-cycles there are in H containing x and a vertex in Z. After that, we will count how many induced 5-cycles there are in \(H[\{u_1,u_2,u_3,w\}\cup Z]\) for each of these assignments. We will then use the second and third points above to calculate the sizes of A, B, and C in each case. We can then use all of this information to determine the total number of induced 5-cycles in H in each case.

For the first of these steps it is sufficient by symmetry to count the induced 5-cycles containing x and a vertex in \(F_1\) for each \(x\in \{a,b,c\}\) and each assignment of a type to \(F_1\). If \(F_1\) is of type 1, then there are clearly no induced 5-cycles containing a and a vertex in \(F_1\), and similarly for b and c. If \(F_1\) is of type 2, containing a single vertex z, then \(u_1zwcu_3\) and \(u_2zwcu_3\) are induced 5-cycles in H. We know there are at most twice as many induced 5-cycles in H containing one of a, b, and c and a vertex in \(F_1\) as there are vertices in \(F_1\), so there are exactly two induced 5-cycles containing c and z, and none containing a and z or b and z.

Finally, if \(F_1\) is of type 3 with \(m\ge 3\) vertices labelled as in the definition of a type 3 face (and Fig. 4c), then H contains the induced 5-cycles \(u_1z_2wbu_2\), \(u_1z_2wcu_3\), \(u_2z_mwau_1\), \(u_2z_mwcu_3\), \(u_1z_1z_iwa\) for \(3\le i\le m\), and \(u_2z_1z_iwb\) for \(2\le i\le m-1\). We have identified \(2\,m\) suitable induced 5-cycles, so as above we know this is all of them. So a and b are each in exactly \(m-1\) induced 5-cycles in H containing a vertex in \(F_1\), and c is exactly in two.

We now determine the number of induced 5-cycles in \(H[\{u_1,u_2,u_3,w\}\cup Z]\) in each case. Note that every induced 5-cycle in this graph contains a vertex of Z, and no induced 5-cycle can contain a vertex of Z from each of \(F_1\), \(F_2\), and \(F_3\). Let \(Z_1\subseteq Z\) be the set of vertices in \(F_1\) as before, and let \(Z_2\subseteq Z\) be the set of vertices in \(F_2\). Then by symmetry it is sufficient to calculate the number of induced 5-cycles in \(H[\{u_1,u_2,u_3,w\}\cup Z_1]\) in each case, and the number of induced 5-cycles in \(H[\{u_1,u_2,u_3,w\}\cup Z_1\cup Z_2]\) which contain vertices from both \(Z_1\) and \(Z_2\) in each case.

We first count the number of induced 5-cycles in \(H[\{u_1,u_2,u_3,w\}\cup Z_1]\). Clearly there are none if \(F_1\) is of type 1 or 2. Suppose \(F_1\) is of type 3 with \(m\ge 3\) vertices labelled as in the definition of a face of type 3. The graph \(H[\{u_1,u_2,u_3,w\}\cup Z_1]\) is illustrated in Fig. 6a, where a red line indicates an edge which may or may not be present.

In this graph \(u_3\) is only adjacent to \(u_1\) and \(u_2\) and these are themselves neighbours, so \(u_3\) is not in an induced 5-cycle in this graph. Next, \(z_1\) is adjacent to all the remaining vertices except w, so it also cannot be in an induced 5-cycle in this graph. If an induced 5-cycle contains w, then it contains exactly two of the vertices \(z_2,\dots ,z_m\), and these two must not be neighbours. The remaining two vertices must be \(u_1\) and \(u_2\), and hence the only possible induced 5-cycle containing w is \(u_1z_2wz_mu_2\). This induced 5-cycle is realised if and only if \(m\ge 4\), or \(m=3\) and \(z_2\) and \(z_3\) are not neighbours.

Now suppose \(\varGamma \) is an induced 5-cycle which does not contain w. Then it must contain at least 3 vertices from \(z_2,\dots ,z_m\). Clearly it cannot only contain vertices from \(z_2,\dots ,z_m\), so it contains at least one of \(u_1\) and \(u_2\). Each of these only has one neighbour in \(\{z_2,\dots ,z_m\}\), so in fact \(\varGamma \) contains both \(u_1\) and \(u_2\). Hence it also contains \(z_2\) and \(z_m\), and the remaining vertex is a common neighbour of these two among \(z_3,\dots ,z_{m-1}\). So for such a cycle to appear we must have \(m=4\), and the edges \(z_2z_3\) and \(z_3z_4\) must be present. This condition is also sufficient for the induced cycle \(u_1z_2z_3z_4u_2\) to appear.

For each assignment of types 1, 2, and 3 to faces \(F_1\) and \(F_2\), we now count the number of induced 5-cycles in \(H[\{u_1,u_2,u_3,w\}\cup Z_1\cup Z_2]\) which contain vertices from both \(Z_1\) and \(Z_2\). If either face is of type 1, then clearly there are no such cycles. If both faces are of type 2, then label the vertex in \(F_1\) as z and the vertex in \(F_2\) as \(z'\). The graph \(H[\{u_1,u_2,u_3,w\}\cup Z_1\cup Z_2]\) is illustrated in Fig. 6b. It is straightforward to see (for example by considering whether or not the cycle contains w) that there is exactly one induced 5-cycle of the required form, namely \(u_1zwz'u_3\).

Now suppose that \(F_1\) is of type 3 with \(m\ge 3\) vertices and \(F_2\) is of type 2. Label the vertices in \(F_1\) as \(z_1,\dots ,z_m\) in the usual way, and the vertex in \(F_2\) as z. The graph \(H[\{u_1,u_2,u_3,w\}\cup Z_1\cup Z_2]\) is illustrated in Fig. 6c, where a red line indicates an edge which may or may not be present.

Let \(\varGamma \) be an induced 5-cycle in the graph containing z and one of \(z_1,\dots ,z_m\). Then since \(\varGamma \) contains z it must also contain w. Suppose \(\varGamma \) contains \(z_1\), then since \(z_1\) is not adjacent to w the cycle must also contain a common neighbour of \(z_1\) and w, i.e. one of \(z_2,\dots ,z_m\). So \(\varGamma \) contains the path \(zwz_iz_1\) for some \(2\le i\le m\). The only common neighbour of z and \(z_1\) is \(u_2\), so \(\varGamma \) is \(zwz_iz_1u_2\) for some \(2\le i\le m\). This induced 5-cycle is realised if and only if \(i\ne m\), so there are exactly \(m-2\) such 5-cycles.

Now suppose \(\varGamma \) does not contain \(z_1\). Then it must contain one of \(z_2,\dots ,z_m\), and since these are all neighbours of w it must in fact contain exactly one of them. For \(3\le i\le m-1\), \(z_i\) has no neighbours outside \(\{w,z_1,\dots ,z_m\}\), so \(\varGamma \) must contain \(z_2\) or \(z_m\). If it contains \(z_m\), then it also contains \(u_2\), but this is a neighbour of z. Hence \(\varGamma \) contains the path \(zwz_2u_1\). The only common neighbours of \(u_1\) and z are \(u_2\) and \(u_3\), and the induced 5-cycle is realised in both cases. So in total there are m induced 5-cycles in the graph containing a vertex from \(Z_1\) and a vertex from \(Z_2\).

Finally, suppose \(F_1\) and \(F_2\) are both of type 3, containing \(m\ge 3\) and \(m'\ge 3\) vertices respectively. Label the vertices in \(F_1\) as \(z_1,\dots ,z_m\) in the usual way, and the vertices in \(F_2\) as \(z'_1,\dots ,z'_{m'}\) in the analogous way, as illustrated in Fig. 6d. As usual, red lines in the figure indicate edges which may or may not be present.

Let \(\varGamma \) be an induced 5-cycle in the graph containing a vertex from \(Z_1\) and a vertex from \(Z_2\). Since \(\varGamma \) contains vertices in both \(F_1\) and \(F_2\), it must contain two vertices on the boundaries of each. Therefore it contains a vertex which is on the boundary of both faces, i.e. w or \(u_2\). If it does not contain w, then in order to contain two vertices on the boundary of each face it must contain \(u_1\), \(u_2\), and \(u_3\) which is impossible. Hence \(\varGamma \) contains w.

Suppose \(\varGamma \) contains \(z_1\). If it does not also contain one of \(z_2,\dots ,z_m\), then it contains \(u_1\) and \(u_2\) as these are the only other vertices adjacent to \(z_1\). But then \(\varGamma \) contains \(u_1\), \(u_2\), and \(z_1\), which form a triangle, giving a contradiction. So \(\varGamma \) contains one of \(z_2,\dots ,z_m\). It cannot contain more than one of \(z_2,\dots ,z_m\) since these are all common neighbours of \(z_1\) and w.

It follows that \(\varGamma \) contains a path \(u_iz_1z_jw\) for some \(i\in \{1,2\}\) and \(j\in \{2,\dots ,m\}\). There are no common neighbours of \(u_1\) and w which are not adjacent to \(z_1\), and the only common neighbour of \(u_2\) and w which is not adjacent to \(z_1\) is \(z'_2\). Hence if \(\varGamma \) contains \(z_1\), then it is of the form \(u_2z_1z_jwz'_2\) for some \(j\in \{2,\dots ,m\}\). This induced 5-cycle is realised if and only if \(j\in \{2,\dots ,m-1\}\), so there are exactly \(m-2\) induced cycles of the required form containing \(z_1\). Similarly there are exactly \(m'-2\) containing \(z'_1\).

Now suppose \(\varGamma \) contains neither \(z_1\) nor \(z'_1\). Then it contains one vertex from \(z_2,\dots ,z_m\) and one from \(z'_2,\dots ,z'_{m'}\). All of these vertices are neighbours of w, so in fact \(\varGamma \) must contain exactly one from each list. The remaining two vertices in \(\varGamma \) must be picked from \(u_1\), \(u_2\), and \(u_3\). None of \(z_3,\dots ,z_{m-1}\) or \(z'_3,\dots ,z'_{m'-1}\) are adjacent to any of these vertices, so the neighbours of w in the cycle must be one of \(z_2\) and \(z_m\) and one of \(z'_2\) and \(z'_{m'}\). For each such combination except \(z_m\) and \(z'_2\), we see there is a single induced 5-cycle of the required form, and for \(z_m\) and \(z'_2\) there are none. So in total there are \(m+m'-1\) induced 5-cycles in the graph containing a vertex in \(Z_1\) and a vertex in \(Z_2\).

To summarise our findings:

• if \(F_1\) is of type 1, then there are no induced 5-cycles containing a vertex in \(F_1\),

• if \(F_1\) is of type 2, then there are no induced 5-cycles containing a or b and a vertex in \(F_1\), and there are exactly two containing c and a vertex in \(F_1\),

• if \(F_1\) is of type 3 with \(m\ge 3\) vertices, then for \(x\in \{a,b\}\) there are exactly \(m-1\) induced 5-cycles containing x and a vertex in \(F_1\), and there are exactly two containing c and a vertex in \(F_1\),

• \(H[\{u_1,u_2,u_3,w\}\cup Z]\) contains exactly

  • one induced 5-cycle per face of type 3 with \(m\ge 5\) vertices, four vertices but not both optional edges present, or three vertices with the optional edge not present,

  • two induced 5-cycles per face of type 3 with four vertices and both optional edges present,

  • one induced 5-cycle per pair of faces of type 2,

  • m induced 5-cycles per pair of faces where one is of type 2 and the other is of type 3 with m vertices,

  • \(m+m'-1\) induced 5-cycles per pair of faces of type 3, where one has m vertices and the other has \(m'\),

  and no further induced 5-cycles.

For each assignment of types to \(F_1\), \(F_2\), and \(F_3\), we can now calculate the sizes of A, B, and C and thence can determine the total number of induced 5-cycles in H in each case. The details of this process are laid out in Appendix A, where the following claim is proved.

Claim 5

H is the principal graph of the required form on n vertices.

Label the vertices of H according to Definition 1. Fix a drawing of G, then by Lemma 4 we may assume that the boundaries of the faces in the induced drawing of H consist of the cycles listed in the statement of that lemma. Consider adding the edges in \(E(G){\setminus } E(H)\) back to this drawing of H. Clearly no edge is added to a triangular face. The remaining faces’ boundaries are cycles of the form \(u_iywy'\) for some \(i\in \{1,2,3\}\) and \(y,y'\in A\cup B\cup C\cup Z\). Hence every edge in \(E(G){\setminus } E(H)\) is of the form \(u_iw\) for some \(i\in \{1,2,3\}\), or \(yy'\) for some \(y,y'\in A\cup B\cup C\cup Z\) such that there exists \(i\in \{1,2,3\}\) such that cycle \(u_iywy'\) appears in the list in Lemma 4. The sets of induced 5-cycles in G and H are the same, and there is an induced 5-cycle in H containing \(u_i\) and w for each \(i\in \{1,2,3\}\), so \(u_iw\not \in E(G){\setminus } E(H)\) for all \(i\in \{1,2,3\}\). Analysing the list of cycles in Lemma 4, we see that G is of the required form.

By Lemma 5, H contains exactly \(\frac{1}{3}(n^2-8n+22)\) induced 5-cycles. We know that G has the same set of induced 5-cycles as H, so G contains exactly \(\frac{1}{3}(n^2-8n+22)\) induced 5-cycles too. \(\square \)