# Planar Turán number of the $7$-cycle

Ruilin Shi  School of Mathematics, Georgia Institute of Technology, USA  Zach
Walsh  School of Mathematics, Georgia Institute of Technology, USA  Xingxing
Yu  School of Mathematics, Georgia Institute of Technology, USA

###### Abstract

The _planar Turán number_ $\operatorname{ex}_{\mathcal{P}}(n,H)$ of a graph
$H$ is the maximum number of edges in an $n$-vertex planar graph without $H$
as a subgraph. Let $C_{\ell}$ denote the cycle of length $\ell$. The planar
Turán number $\operatorname{ex}_{\mathcal{P}}(n,C_{\ell})$ behaves differently
for $\ell\leq 10$ and for $\ell\geq 11$, and it is known when
$\ell\in\\{3,4,5,6\\}$. We prove that
$\operatorname{ex}_{\mathcal{P}}(n,C_{7})\leq\frac{18n}{7}-\frac{48}{7}$ for
all $n>38$, and show that equality holds for infinitely many integers $n$.

##  1 Introduction

The _Turán number_ $\operatorname{ex}(n,H)$ of a graph $H$ is the maximum
number of edges in an $n$-vertex graph without $H$ as a subgraph. Turán’s
theorem [13], a cornerstone of extremal graph theory, states that
$\operatorname{ex}(n,K_{t})\leq(1-\frac{1}{t-1}){n\choose 2}$ for all integers
$t$ and $n$ with $n,t\geq 3$, with equality for balanced complete
$(t-1)$-partite graphs. This has led to a huge amount of related work,
including the Erdős-Stone theorem [4], generalized Turán numbers (see [1]),
and Turán problems for hypergraphs (see [7]).

Another well-studied variant of Turán’s theorem involves placing restrictions
on the host graph; for example, forcing the host graph to be a hypercube (see
[11]) or an Erdős-Rényi random graph (see [12]). In 2015, Dowden considered
the variant in which the host graph is planar, and defined the _planar Turán
number_ $\operatorname{ex}_{\mathcal{P}}(n,H)$ of a graph $H$ to be the
maximum number of edges in an $n$-vertex planar graph without $H$ as a
subgraph [3]. For example, it follows from Euler’s formula that
$\operatorname{ex}_{\mathcal{P}}(n,C_{3})=2n-4$ for all $n\geq 3$, where
$C_{\ell}$ denotes the cycle of length $\ell$. Since cycles are arguably the
most natural choice for $H$ in the planar setting, Dowden proved that
$\operatorname{ex}_{\mathcal{P}}(n,C_{4})\leq\frac{15(n-2)}{7}$ for all $n\geq
4$ and $\operatorname{ex}_{\mathcal{P}}(n,C_{5})\leq\frac{12n-33}{5}$ for all
$n\geq 11$, and showed that in both cases equality holds infinitely often [3].
This initiated a flurry of research on planar Turán numbers. We direct the
reader to the survey paper of Lan, Shi, and Song [9] for details regarding
recent related work, while we continue to focus on the planar Turán number of
$C_{\ell}$.

In [5], Ghosh, Győri, Martin, Paulos, and Xiao took the next step and proved
that $\operatorname{ex}_{\mathcal{P}}(n,C_{6})\leq\frac{5n}{2}-7$ with
equality holding infinitely often, improving upon a result of Yan, Shi, and
Song [8]. They also conjectured that
$\operatorname{ex}_{\mathcal{P}}(n,C_{\ell})\leq\frac{3(\ell-1)}{\ell}n-\frac{6(\ell+1)}{\ell}$
for all $\ell\geq 7$ and all sufficiently large $n$, as this is the correct
bound for $\ell\in\\{5,6\\}$. If true, this bound would be tight infinitely
often for every $\ell\geq 7$. However, this conjecture was disproved for all
$\ell\geq 11$ by Cranston, Lidický, Liu, and Shantanam [2], and later also by
Lan and Song [10], using the fact that planar triangulations with at least
$11$ vertices need not be Hamiltonian. While the correct value of
$\operatorname{ex}_{\mathcal{P}}(n,C_{\ell})$ is rather mysterious for
$\ell\geq 11$ (see [2] and [10]), we prove the conjecture of Ghosh et al. in
the case that $\ell=7$ (writing $e(G)$ for the number of edges of a graph
$G$).

######  Theorem 1.1.

Let $n$ be an integer with $n>38$ and let $G$ be an $n$-vertex $C_{7}$-free
planar graph. Then $e(G)\leq\frac{18}{7}n-\frac{48}{7}$, and equality holds
infinitely often.

The condition that $n>38$ is necessary, due to the $38$-vertex graph obtained
by gluing $18$ copies of $K_{4}$ together on a common edge.

We next describe, for each $\ell\geq 5$ and for infinitely many $n$, a
$C_{\ell}$-free $n$-vertex planar graph with
$\frac{3(\ell-1)}{\ell}n-\frac{6(\ell+1)}{\ell}$ edges, following Cranston et
al. [2]. Let $G$ be an $n$-vertex planar graph with girth $\ell+1$, each
vertex having degree 2 or $3$, and $\frac{\ell+1}{\ell-1}(n-2)$ edges; such a
graph exists for infinitely many integers $n$ [2, Lemma 2]. Let $G^{\prime}$
be obtained from $G$ by _substituting_ an $(\ell-1)$-vertex planar
triangulation $B$ for each vertex of $G$, which means that each vertex $v$ of
$G$ is replaced by a copy of $B$ and $\deg_{G}(v)$ vertices of $B$ on a facial
triangle are identified with the neighbors of $v$ in $G$. Then $G^{\prime}$ is
a $C_{\ell}$-free $n^{\prime}$-vertex graph with
$\frac{3(\ell-1)}{\ell}n^{\prime}-\frac{6(\ell+1)}{\ell}$ edges [2, Corollary
5]. In particular, if $\ell=7$ then $G^{\prime}$ is a $C_{7}$-free
$n^{\prime}$-vertex graph with $\frac{18}{7}n^{\prime}-\frac{48}{7}$ edges, so
the bound in Theorem 1.1 holds infinitely often.

To prove Theorem 1.1 it suffices to consider graphs without small separations,
and without small sets of vertices with only a few incident edges. For a graph
$G$ and constant $\alpha>0$, a set $S\subseteq V(G)$ is $\alpha$-sparse if $G$
has at most $\alpha|S|$ edges with at least one incident vertex in $S$. For
each positive integer $n$, we write $\mathcal{P}_{n}$ for the class of
$n$-vertex, $2$-connected, $C_{7}$-free plane graphs with no (18/7)-sparse set
of order at most 4. We will obtain Theorem 1.1 as a consequence of the
following result, by generating all $C_{7}$-free planar graphs from
$\cup_{i\geq 1}\mathcal{P}_{i}$ through several basic operations.

######  Theorem 1.2.

Let $G\in\mathcal{P}_{n}$ with $n\geq 7$. Then
$e(G)\leq\frac{18}{7}n-\frac{48}{7}$.

Our proof uses the same strategy employed by Ghosh et al. in [5] to find
$\operatorname{ex}_{\mathcal{P}}(n,C_{6})$, as we believe it is the natural
approach. We also use their terminology whenever possible, for consistency.
This terminology and the proof strategy are both described in Section 2. We
also enhance their strategy with a result (Lemma 3.1) about long paths in near
triangulations which we believe will be useful for other planar Turán
problems.

For a graph $G$, we use $V(G)$ and $E(G)$ to denote its vertex set and edge
set, respectively, and often write $|G|$ for $|V(G)|$ and $e(G)$ for $|E(G)|$.
For any $S\subseteq V(G)$, we use $G[S]$ to denote the subgraph of $G$ induced
by $S$ and write $G-S$ for $G[V(G)\setminus S]$ (and write $G-s$ instead of
$S=\\{s\\}$). For any subgraph $H$ of $G$, we write $G-H$ for $G-V(H)$. For a
subgraph $B$ of a graph of $G$, a _$B$ -path_ is a path in $G$ that has both
ends in $B$ and is internally disjoint from $B$. A $B$-path of length 1 is
also known as a chord of $B$. For any positive integer $k$, we let
$[k]=\\{1,\ldots,k\\}$.

If $G$ is a plane graph, then $F(G)$ denotes its set of faces. It is well
known that if $G$ is a 2-connected plane graph then each member of $F(G)$ is
bounded by a cycle. The interior of a cycle $C$ in a plane graph is defined to
be the subgraph of $G$ consisting of all edges and vertices of $G$ contained
in the closed disc of the plane bounded by $C$. Paths and cycles will be
represented as a sequence of vertices such that consecutive vertices in the
sequence are adjacent. For instance, $x_{1}x_{2}x_{3}\ldots x_{k}$ is a path
of length $k-1$, and $x_{1}x_{2}x_{3}\ldots x_{k}x_{1}$ is a cycle of length
$k$. For any distinct vertices $x,y$ in a graph $G$, we use $d(x,y)$ to denote
the distance between $x$ and $y$ in $G$, and if $x,y$ are on a path $P$ then
$xPy$ denotes the subpath of $P$ between $x$ and $y$. For any cycle $C$ in a
plane graph and any two distinct vertices $x,y$ on $C$, we use $xCy$ to denote
the subpath of $C$ from $x$ to $y$ in clockwise order.

##  2 Proof strategy and triangular-blocks

We now describe the proof strategy for Theorem 1.1, which is based on that of
Ghosh et al [5]. If $G$ is a connected $n$-vertex plane graph with $e$ edges
and $f$ faces, then $e\leq\frac{18n}{7}-\frac{48}{7}$ is equivalent via
Euler’s formula to

$24f-17e+6n\leq 0,$

by replacing the 48 with $24(n-e+f)$. We will decompose the graph $G$ into
edge-disjoint subgraphs, and show that no subgraph contributes too much
towards the left-hand side of the inequality. Due to the extremal
construction, it is natural to decompose $G$ into unions of facial triangles.
For facial triangles $F$ and $F^{\prime}$ of $G$ we say that $F\sim
F^{\prime}$ if there is a sequence $F=F_{1},F_{2},\dots,F_{k}=F^{\prime}$ of
facial triangles of $G$ so that for each $i\in[k-1]$, $F_{i}$ and $F_{i+1}$
share an edge. Clearly $\sim$ is an equivalence relation on the facial
triangles of $G$. This motivates the following key definition [5].

######  Definition 2.1.

Let $G$ be a plane graph. For $e\in E(G)$, if $e$ is not contained in any
facial triangle, then let $B(e)$ be the 2-vertex subgraph of $G$ induced by
$e$; otherwise, let $B(e)$ denote the union of all facial triangles equivalent
to some facial triangle containing $e$. We call $B(e)$ the _triangular-block_
containing $e$, and it is _trivial_ if $B(e)$ has just two vertices. We use
$\mathcal{B}(G)$ to denote the collection of all triangular-blocks of $G$.

It is clear from the definition that if $B$ is a triangular-block of $G$ and
$e_{1}$ and $e_{2}$ are distinct edges of $B$, then $B=B(e_{1})=B(e_{2})$. In
particular, any two distinct triangular-blocks of $G$ are edge-disjoint. Also,
note that any redrawing of $G$ with the same set of faces has the same
triangular-blocks. However, note that a face of a triangular-block $B$ is not
necessarily a face of $G$. For example, the interior $4$-face of $B_{7,b}$ in
Figure 5 need not be a face of $G$.

######  Definition 2.2.

Let $B$ be a triangular-block of a plane graph $G$. A _hole_ of $B$ is a face
of $B$ that is not a face of $G$.

Not every face of a triangular-block can be a hole. We next make two useful
observations about faces of triangular-blocks.

######  Lemma 2.3.

Let $G$ be a $2$-connected plane graph and let $B$ be a triangular-block of
$G$ whose outer face is a hole. Let $C$ be the outer cycle of $B$ and let $P$
be a $C$-path in $B$. Then some edge of $P$ is in two facial triangles of $G$.

###### Proof.

Let $P_{1}$ and $P_{2}$ be the two subpaths of $C$ for which $P_{1}\cup P$ and
$P_{2}\cup P$ are cycles. Since the outer face of $B$ is a hole, each facial
triangle of $B$ that is a facial triangle of $G$ is in the interior of either
$P_{1}\cup P$ or $P_{2}\cup P$. If no edge of $P$ is in two facial triangles,
then no facial triangle of $G$ in the interior of $P_{1}\cup P$ is equivalent
under $\sim$ to a facial triangle of $G$ in the interior of $P_{2}\cup P$, a
contradiction. ∎

The following is a useful consequence of Lemma 2.3.

######  Lemma 2.4.

Let $B$ be a triangular-block of a $2$-connected plane graph $G$, and let
$F_{1}$ and $F_{2}$ be facial cycles of $B$ that each have length at least
four. Then $F_{1}$ and $F_{2}$ share at most one vertex.

###### Proof.

By redrawing $G$, we may assume that $F_{1}$ is the outer cycle of $G$. If the
statement is false, then there are vertices $a$ and $b$ in $V(F_{1})\cap
V(F_{2})$ and an $a$-$b$ path $P$ in the interior of $F_{1}$ so that
$E(P)\subseteq E(F_{2})$. But by Lemma 2.3 this is a contradiction. ∎

The proof strategy for Theorem 1.1 is to show that no triangular-block of $G$
contributes too much towards the sum $24f-17e+6n$. We next make several
definitions, following Ghosh et al. [5], to describe how a triangular-block
contributes to $24f-17e+6n$. This is easy for edges: each triangular-block $B$
contributes $e(B)$ towards $e$. Then

$\sum_{B\in\mathcal{B}(G)}e(B)=e,$

since triangular-blocks are pairwise edge-disjoint. We next describe the
contribution of a triangular-block $B$ to $n$.

######  Definition 2.5.

Let $G$ be a plane graph and $v\in V(G)$. We write
$\mathcal{B}(G)_{v}=\\{B\in\mathcal{B}(G):v\in V(B)\\}$ and say that $v$ is a
_junction vertex_ if $|\mathcal{B}(G)_{v}|>1$. We define
$n(v)=1/|\mathcal{B}(G)_{v}|$, and $n(B)=\sum_{v\in V(B)}n(v)$.

Thus, for an $n$-vertex plane graph $G$,

$\sum_{B\in\mathcal{B}(G)}n(B)=\sum_{B\in\mathcal{B}(G)}\sum_{v\in
V(B)}n(v)=\sum_{v\in V(G)}\sum_{B\in\mathcal{B}(G)_{v}}n(v)=n.$

We next define the contribution of a triangular-block to the number of faces
of a plane graph $G$. To do this we must develop some notation concerning the
faces incident with edges of a triangular-block $B$.

######  Definition 2.6.

Let $B$ be a triangular-block of a $2$-connected plane graph $G$. A facial
cycle $F$ of $G$ that is not a facial cycle of $B$ but shares edges with $B$
is a _petal_ of $B$. The petal $F$ is said to be _leaky_ if the graph $F\cap
B$ is disconnected. The subgraph of $G$ consisting of $B$ and all petals of
$B$ is the _flower_ of $B$.

Our next definition will help deal with a facial cycle that intersects a
triangular-block in a path with a least two edges.

######  Definition 2.7.

Let $G$ be a $2$-connected plane graph and let $F$ be a facial cycle of $G$. A
triple $x_{1}x_{2}x_{3}$ of consecutive vertices on $F$ is a _bad cherry_ if
$x_{1}x_{3}\in E(G)\setminus E(F)$ and $x_{1}$ and $x_{3}$ are junction
vertices of a triangular-block of $G$ that also contains the triangle
$x_{1}x_{2}x_{3}x_{1}$. Let $F^{\prime}$ be the cycle obtained from $F$ in the
following manner: for each bad cherry $x_{1}x_{2}x_{3}$ of $F$, replace the
path $x_{1}x_{2}x_{3}$ in $F$ with the path $x_{1}x_{3}$. We say that
$F^{\prime}$ is the _refinement_ of $F$. For convenience, let $F^{\prime}=F$
if $F$ has no bad cherry.

Note that the refinement $F^{\prime}$ of a facial cycle $F$ in a plane graph
$G$ is a cycle which has length at most $|F|-1$ except when $F^{\prime}=F$
(i.e., $F$ has no bad cherry). Also, it is straightforward to check that if
$G$ is $C_{7}$-free and $|F|\geq 8$, then $|F^{\prime}|\geq 8$ as well; we
freely use this fact. We can now define the contribution of a triangular-block
of a plane graph $G$ to the number of faces of $G$.

######  Definition 2.8.

Let $G$ be a $2$-connected plane graph. Let $B$ be a triangular-block of $G$
and let $\mathcal{P}(B)$ be the set of petals of $B$. Let $F\in\mathcal{P}(B)$
and let $F^{\prime}$ be the refinement of $F$. Define $f_{F}(B)=e(F\cap
B)/e(F^{\prime})$ if $F\cap B$ is not a bad cherry, and
$f_{F}(B)=1/e(F^{\prime})$ if $F\cap B$ is a bad cherry. Finally, define

$f(B)=(\textrm{number of non-hole faces of
$B$})+\sum_{F\in\mathcal{P}(B)}f_{F}(B).$

It is not hard to check that if $G$ is a $2$-connected plane graph then
$|F(G)|=\sum_{B\in\mathcal{B}(G)}f(B)$.

Now that we have defined the contribution of a triangular-block to edges,
vertices, and faces, we can define the contribution of a triangular-block to
$24f-17e+6n$.

######  Definition 2.9.

Let $G$ be a $2$-connected plane graph, and let $B$ be a triangular-block of
$G$. We define

$g(B)=24f(B)-17e(B)+6n(B).$

We comment that $g(B)$ will be independent of the planar drawing of $G$ we
choose as all planar drawings of $G$ we use will have the same collection of
faces and facial cycles. So when we compute an estimate for $g(B)$ we may work
with a particular planar drawing of $G$ that is most convenient and therefore
of $B$ as well. Also note that if $G$ has $n$ vertices, $e$ edges, and $f$
faces, then $\sum_{B\in\mathcal{B}(G)}g(B)=24f-17e+6n$. This leads to the
following proof strategy for Theorem 1.1: show that each triangular-block $B$
of $G$ satisfies $g(B)\leq 0$. However, there are two exceptional cases, shown
in Figure 6, for which $g(B)>0$. To deal with these cases we will instead find
a partition of $\mathcal{B}(G)$ so that the sum of $g(B)$ for the triangular-
blocks in each part of the partition is at most zero. Then Theorem 1.1 will
follow from the following lemma, which was also proved in [5].

######  Lemma 2.10.

Let $G$ be a $2$-connected $n$-vertex plane graph. If there is a partition
$\mathcal{P}=\\{\mathcal{B}_{1},\mathcal{B}_{2},\dots,\mathcal{B}_{m}\\}$ of
$\mathcal{B}(G)$ so that $\sum_{B\in\mathcal{B}_{i}}g(B)\leq 0$ for all
$i\in[m]$, then $e(G)\leq\frac{18n}{7}-\frac{48}{7}$.

###### Proof.

The statement follows from the facts that
$\sum_{B\in\mathcal{B}(G)}g(B)=24f(G)-17e(G)+6n$, and
$e(G)\leq\frac{18n}{7}-\frac{48}{7}$ if and only if $24f(G)-17e(G)+6n\leq 0$.
∎

In order to apply this lemma we must characterize the possible triangular-
blocks of a $C_{7}$-free plane graph and then estimate $g(B)$ for each such
triangular-block $B$. In Section 3 we prove some properties about paths in
triangular-blocks, and in Section 4 we characterize the possible triangular-
blocks of a $C_{7}$-free plane graph. Then in Sections 5-7 we bound $g(B)$ for
each possible $C_{7}$-free triangular-block $B$. We prove Theorem 1.2 in
Section 8 and then prove Theorem 1.1 in Section 9. We finish by discussing
some related open problems in Section 10.

##  3 Near Triangulations

A _near triangulation_ is a plane graph in which every face is bounded by a
triangle except possibly the outer face. Note that any near-triangulation is
an iterative union of facial triangles, and could therefore be a triangular-
block of a plane graph. For convenience, we allow any planar embedding of
$K_{2}$ to be a near triangulation with itself as its outer cycle. In this
section we prove two lemmas that will help us characterize all possible
$C_{7}$-free triangular-blocks of a plane graph, and also help us bound $g(B)$
for a given triangular-block $B$.

######  Lemma 3.1.

Let $G$ be a near triangulation with outer cycle $C$, and let $x,y\in V(C)$ be
distinct. Suppose $G$ contains an $x$-$y$ Hamiltonian path. Then $G$ also
contains an $x$-$y$ path of length $\ell$ for all $\ell$ with
$d(x,y)\leq\ell\leq|V(G)|-1$.

###### Proof.

We apply induction on $n:=|V(G)|\geq 2$. The assertion is easily seen to be
true for $n=2$ and $n=3$. So assume $n\geq 4$.

Case 1\. $G-x$ is 2-connected.

Then $G-x$ is also a near triangulation. Let $D$ denote the outer cycle of
$G-x$. Let $x_{1},x_{2},\ldots,x_{k}$ be the neighbors of $x$ and assume that
$x_{1},x_{2},\ldots,x_{k},y$ occur on $D$ clockwise in the order listed. Then
$x_{1},x_{k}\in V(C)$, $x_{1}Dx_{k}=x_{1}x_{2}\ldots x_{k}$, and
$x_{k}Cx_{1}=x_{k}Dx_{1}$.

Without loss of generality, we may assume that some $x$-$y$ Hamiltonian path
in $G$ uses the edge $xx_{t}$ for some $t\in[k]$. Then $G-x$ has a Hamiltonian
$x_{t}$-$y$ path. Hence, by induction, $G-x$ contains an $x_{t}$-$y$ path of
any length between $d_{G-x}(x_{t},y)$ and $n-2$. So by adding the edge
$xx_{t}$, we see that $G$ has an $x$-$y$ path of any length between
$d_{G-x}(x_{t},y)+1$ and $n-1$. We are done if $d_{G-x}(x_{t},y)\leq
d_{G}(x,y)-1$. So assume $d_{G-x}(x_{t},y)\geq d_{G}(x,y)$.

Let $P$ be a shortest $x$-$y$ path in $G$, i.e., the length of $P$ is
$d_{G}(x,y)$, and let $xx_{s}\in E(P)$, where $s\in[k]$. Then for all
$i\in[k]\setminus\\{s\\}$, $x_{i}\notin V(P)$; otherwise, $xx_{i}\cup x_{i}Py$
would be an $x$-$y$ path in $G$ shorter than $P$. Let $Q$ denote the subpath
of $x_{1}Dx_{k}$ between $x_{s}$ and $x_{t}$. Then $Q\cup P$ is an $x_{t}$-$y$
path in $G-x$ of length $d_{G}(x,y)-1+|s-t|$. Hence, $d_{G-x}(x_{t},y)\leq
d_{G}(x,y)-1+|s-t|$. Thus, $G$ has an $x$-$y$ path of any length between
$d_{G}(x,y)+|s-t|$ and $n-1$.

Therefore, it remains to show that $G$ has $x$-$y$ paths of any length between
$d_{G}(x,y)$ and $d_{G}(x,y)-1+|s-t|$. For each $x_{i}\in V(Q)$ we see that
$P_{i}:=xx_{i}\cup x_{i}Qx_{s}\cup(P-x)$ is an $x$-$y$ path in $G$ of length
$d_{G}(x,y)+|i-s|$. Thus, the paths $P_{i}$, for all $x_{i}\in V(Q)$, are
$x$-$y$ paths of all possible lengths between $d_{G}(x,y)$ and
$d_{G}(x,y)+|s-t|$.

Case 2\. $G-x$ is not 2-connected.

Then, since $G$ is a near triangulation, $C$ has chords from $x$ to $C-x$.
Since $G$ has a Hamiltonian $x$-$y$ path, the chords of $C$ from $x$ must all
end on $xCy-\\{x,y\\}$ or all end on $yCx-\\{x,y\\}$. By symmetry, we may
assume that all chords of $C$ from $x$ end on $xCy$, and let $xz$ be the chord
of $C$ with $zCy$ minimal.

Let $C_{1}:=xCz\cup zx$ and $C_{2}:=zCx\cup xz$, which are two cycles in $G$.
For $i\in[2]$, let $G_{i}$ denote the interior of $C_{i}$. Then each $G_{i}$
is a near triangulation and $C_{i}$ is its outer cycle. Observe that any
$x$-$y$ Hamiltonian path in $G$ gives rise to an $x$-$z$ Hamiltonian path in
$G_{1}$, as well as a $z$-$y$ Hamiltonian path in $G_{2}-x$ (and hence a
$x$-$y$ Hamiltonian path in $G_{2}$ by adding the edge $xz$). Moreover,
$d_{G_{2}}(x,y)=d_{G}(x,y)$. Let $n_{i}:=|V(G_{i})|$ for $i\in[2]$.

By induction, $G_{1}$ has an $x$-$z$ path of length $\ell_{1}$ for every
$\ell_{1}$ between $d_{G_{1}}(x,z)=1$ and $n_{1}-1$, and $G_{2}$ has an
$x$-$y$ path of length $\ell_{2}$ for every $\ell_{2}$ between
$d_{G_{2}}(x,y)=d_{G}(x,y)$ and $n_{2}-1$. It remains to show that $G$ has
$x$-$y$ paths of any length between $n_{2}$ and $n-1$.

Let $P$ be a Hamiltonian $z$-$y$ path in $G_{2}-x$. Thus, the length of $P$ is
$n_{2}-2$. Now take an $x$-$z$ path $P_{m}$ in $G_{1}$ of length $m$ for each
$m\in[n_{1}-1]$. Then for $m\in[n_{1}-1]$, $P\cup P_{m}$ is an $x$-$y$ path of
length $m+n_{2}-1$. Noting that $n=n_{1}+n_{2}-1$, we see that $G$ has an
$x$-$y$ path of any length between $n_{2}$ and $n-1$. ∎

$y$$x$ | $y$$x$ | $x$$y$
---|---|---
$B_{6,a}$ | $B_{6,c}$ | $B_{6,d}$
Figure 1: The three exceptional cases for Lemma 3.2.

Next, we consider near triangulations with at most six vertices. Such a graph
is certainly $C_{7}$-free, and is therefore relevant for the proof of Theorem
1.1.

######  Lemma 3.2.

Let $G$ be a near triangulation with outer cycle $C$, and let $x,y\in V(C)$ be
distinct. Suppose $|V(G)|\leq 6$. Then $G$ contains an $x$-$y$ Hamiltonian
path or one of the following holds:

  * $(i)$

$xy$ is a chord of $C$.

  * $(ii)$

$G$ has a path $xzy$ such that both $xz$ and $zy$ are chords of $C$, and
$G-\\{x,y,z\\}$ consists of 3 isolated vertices (so $G\cong B_{6,a}$ or
$G\cong B_{6,d}$ with $x,y$ as in Figure 1).

  * $(iii)$

$G\cong B_{6,c}$ with $x$, $y$ as in Figure 1.

###### Proof.

Suppose for a contradiction that the assertion is false, and let $G$ be a
counterexample with $|V(G)|$ minimum. Then $|V(G)|\geq 4$, as otherwise $G$
contains an $x$-$y$ Hamiltonian path. Moreover, $xy$ is not a chord of $C$; as
otherwise we have $(i)$.

Observe that if $G$ contains a chord from $x$ to $xCy-x$ and a chord from $x$
to $yCx-x$, then since $|V(G)|\leq 6$ (and because of planarity), $G$ has no
chord from $y$ to $xCy-y$ or $yCx-y$. Hence, we may assume by symmetry
(between $x$ and $y$ and between $xCy$ and $yCx$) that $G$ has no chord from
$x$ to $yCx-x$.

Since $xy$ is not a chord of $C$ and $G$ is a near triangulation, $y$ is not a
cut vertex of the connected graph $G-x$. So let $Y$ denote the unique block of
$G-x$ containing $y$. Let $x_{1},x_{2}\in V(Y)\cap V(C-x)$ such that
$x,x_{1},y,x_{2}$ occur in $C$ in clockwise order, and $x_{1}Cx_{2}=Y\cap C$.
Since $G$ has no chord from $x$ to $yCx-x$, we see that $x_{2}x\in E(C)$. Let
$X:=G-(Y-x_{1})$. Note that if $|V(X)|\geq 3$ then $X$ is a near triangulation
with outer cycle $C_{X}:=xCx_{1}\cup x_{1}x$, and that if $|V(Y)|\geq 3$ then
$Y$ is a near triangulation and its outer cycle, denoted $C_{Y}$, satisfies
$x_{1}Cx_{2}=x_{1}C_{Y}x_{2}$.

We may assume $y\neq x_{1}$. For otherwise, $V(X)=\\{x,y\\}$ as $xy$ is not a
chord of $C$. But then $x_{1}$ and $x_{2}$ are symmetric, and we can relabel
$x_{1},x_{2}$ and flip the embedding of $G$.

Now suppose $|V(G)|\leq 5$. Then $|V(X)|\leq 4$ and $|V(Y)|\leq 4$. Hence, $X$
has an $x$-$x_{1}$ Hamiltonian path (since $xx_{1}$ is not a chord of $C_{X}$)
and, thus, $Y$ has no $x_{1}$-$y$ Hamiltonian path. Hence, $Y$ consists of a
4-cycle $x_{1}aybx_{1}$ and chord $x_{1}y$, and we have $V(X)=\\{x,x_{1}\\}$.
Choose the labeling so that $x_{1}ay\subseteq x_{1}Cx_{2}$. Since $x_{2}x\in
E(C)$ and $G$ is a near triangulation, $xb\in E(G)$. But then $xbx_{1}ay$ is a
$x$-$y$ Hamiltonian path in $G$, a contradiction.

Thus, $|V(G)|=6$. Then $|V(X)|\leq 5$. Hence, by the minimality of $G$, $X$
has an $x$-$x_{1}$ Hamiltonian path (since $xx_{1}$ is not a chord of
$C_{X}$). Therefore, $Y$ has no $x_{1}$-$y$ Hamiltonian path. Thus $|V(X)|=3$
and $|V(Y)|=4$, or $|V(X)|=2$ and $|V(Y)|=5$. Moreover, by the minimality of
$G$, $x_{1}y$ is a chord of $C_{Y}$. If $|V(X)|=3$ and $|V(Y)|=4$ then
$xx_{1},x_{1}y$ are both chords of $C$, and $(ii)$ holds.

So $|V(Y)|=5$ and $|V(X)|=2$. Note that, for any $w\in
V(yC_{Y}x_{1})\setminus\\{y,x_{1}\\}$ with $w\in N(x)$, $Y$ has no $w$-$y$
Hamiltonian path, as such a path and $xw$ would give an $x$-$y$ Hamiltonian
path in $G$. Thus, since $x_{1}y$ is a chord of $C_{Y}$, we have
$|V(C_{Y})|=5$ and $yC_{Y}x_{1}=yvx_{2}x_{1}$ is a path of length 3. Now
$vx_{1}\notin E(G)$, as otherwise $xx_{2}vx_{1}\cup x_{1}C_{Y}y$ is an $x$-$y$
Hamiltonian path in $G$, a contradiction. Hence, $x_{2}y\in E(G)$, which shows
that $(iii)$ holds. ∎

##  4 $C_{7}$-Free Triangular-Blocks

|  |  |
---|---|---|---
$B_{2}$ | $B_{3}$ | $B_{4,a}$ | $B_{4,b}$
Figure 2: Possible triangular-blocks on at most four vertices (up to redrawing) |  |  |
---|---|---|---
$B_{5,a}$ | $B_{5,b}$ | $B_{5,c}$ | $B_{5,d}$
Figure 3: Possible $5$-vertex triangular-blocks (up to redrawing) |  |
---|---|---
$B_{6,a}$ | $B_{6,b}$ | $B_{6,c}$
|  |
$B_{6,d}$ | $B_{6,e}$ | $B_{6,f}$
|  |
$B_{6,g}$ | $B_{6,h}$ | $B_{6,i}$
Figure 4: Possible $6$-vertex triangular-blocks with a chord (up to redrawing) |
---|---
$B_{7,a}$ | $B_{7,b}$
Figure 5: Possible $7$-vertex $C_{7}$-free triangular-blocks (up to redrawing)

In this section we characterize all possible triangular-blocks in a
$C_{7}$-free plane graph, up to redrawings that preserve all facial cycles.
Certainly any near triangulation with at most six vertices is a candidate. In
fact, the following corollary of Lemma 2.4 shows that these are the only
possible triangular-blocks with at most six vertices.

######  Lemma 4.1.

Let $G$ be a $2$-connected plane graph and let $B$ be a triangular-block of
$G$ with at most six vertices. Then $B$ is a near triangulation, up to
redrawings that preserve all facial cycles.

Figures 2, 3, and 4 list all near triangulations with at most five vertices
and all six-vertex near triangulations with a chord. We next prove that there
are only two possible $C_{7}$-free triangular-blocks with more than six
vertices; these are shown in Figure 5.

######  Lemma 4.2.

Every $C_{7}$-free triangular-block of a $2$-connected plane graph $G$ has at
most six vertices, with the exceptions of $B_{7,a}$ and $B_{7,b}$ as in Figure
5.

###### Proof.

Let $B$ be a $C_{7}$-free triangular-block of $G$ with at least seven
vertices.

Suppose $B$ contains a $7$-vertex triangular-block $B_{7,a}$ or $B_{7,b}$.
Note that triangular faces of $B_{7,a}$ and $B_{7,b}$ are not holes, by Lemma
2.3. We may assume that $G$ is drawn so that the $B_{7,a}$ or $B_{7,b}$ in $B$
are drawn as in Figure 5. If $B$ has more than seven vertices, then $B$ has a
plane subgraph obtained by adding a vertex adjacent to both ends of an edge on
a non-triangular facial cycle of $B_{7,a}$ or $B_{7,b}$. It is straightforward
to check that any graph of this form contains $C_{7}$, a contradiction.
Therefore $B\in\\{B_{7,a},B_{7,b}\\}$. Hence, we may assume that $B$ contains
neither $B_{7,a}$ nor $B_{7,b}$.

Note that $B$ has a subgraph $H$ that is obtained from a $6$-vertex
triangular-block $B^{\prime}$ by adding a vertex $z$ that is adjacent to both
vertices of an edge $xy$ of some facial cycle of $B^{\prime}$ bounding a hole
of $B^{\prime}$.

Since $B$ is $C_{7}$-free, $B^{\prime}$ has no $x$-$y$ Hamiltonian path. By
Lemma 4.1, $B^{\prime}$ is a near triangulation, and Lemma 3.2 implies that
$B^{\prime}$ is not a triangulation. By redrawing $G$ we may assume that the
outer cycle $F_{1}$ of $B^{\prime}$ has length at least four. Lemma 3.2
implies that if $xy$ is an edge on the outer cycle of $B^{\prime}$, then
$B^{\prime}\cong B_{6,d}$ and $H=B_{7,a}$, a contradiction. So $xy$ is
incident to an interior triangular hole of $B^{\prime}$. This implies that $H$
has another facial cycle, $F_{2}$, of length at least four. By Lemma 2.4,
$|F_{1}|=|F_{2}|=4$ and $|V(F_{1})\cap V(F_{2})|=1$. Let $F_{1}=abcda$ and
$F_{2}=auvwa$.

Suppose that $F_{1}$ has no chord in its interior. Note that each interior
face of $H$ is triangular except for $F_{2}$. If $ab$ and $bc$ are incident
with the same interior triangular face of $H$, then $ac$ is a chord of $H$, a
contradiction. Since $ab$ and $bc$ are incident with different interior faces,
there is an interior edge of $H$ with $b$ as an end and with the other end in
the set $\\{u,v,w\\}$. However, neither $bu$ nor $bw$ is an edge of $H$;
otherwise, $H$ (and hence $G$) would contain $C_{7}$. So $bv$ is an edge of
$H$. By symmetry, $dv$ is an edge of $H$ and $du$ and $dw$ are not edges of
$H$. The $4$-cycles $abvua$ and $advwa$ each bound two triangular faces of
$H$, which forces $av$ to be an edge in the interior of both $abvua$ and
$advwa$. This is a contradiction.

Thus, we may assume that $F_{1}$ has a chord in its interior. Figure 4 shows
all possible $6$-vertex triangular-blocks whose outer cycle has length four
and has a chord in its interior, and only $B_{6,g}$ and $B_{6,h}$ could have
an interior hole. This hole is bounded by a facial cycle $F$ of $B^{\prime}$
containing both interior vertices of $B^{\prime}$. It is not hard to check
that for any distinct $s,t\in V(F)$, $B^{\prime}$ has an $s$-$t$ Hamiltonian
path, with one exception (when $B^{\prime}\cong B_{6,g}$, $s\in V(F_{1})$, and
$t$ is of degree $4$ in $B^{\prime}$) that results in $H=B_{7,b}$. ∎

We will also need the following characterization of bad cherries in facial
cycles with length at most six.

######  Lemma 4.3.

Let $G$ be a $2$-connected plane graph, let $F$ be a petal of some triangular-
block $B$ of $G$ with $4\leq|F|\leq 6$ and $|B|\geq 3$, and let $F^{\prime}$
be the refinement of $F$. Then $F=F^{\prime}$, unless

  1. $(i)$

$B\in\\{B_{5,d},B_{6,g},B_{6,h},B_{7,b}\\}$,

  2. $(ii)$

$F=wx_{1}x_{2}x_{3}$ where $x_{1}x_{2}x_{3}$ is a bad cherry on the outer
cycle of $B$, and

  3. $(iii)$

$wx_{1}$ and $wx_{3}$ are trivial triangular-blocks incident with exactly one
face of $G$ with length less than eight.

###### Proof.

Assume that $F\neq F^{\prime}$. Then $F$ has a bad cherry $x_{1}x_{2}x_{3}$.
By the definition of bad cherry, $x_{1},x_{2},x_{3}$ are in a common
triangular-block $B$ of $G$. We may assume that $G$ is drawn so that
$x_{1}x_{2}x_{3}$ is contained in the outer cycle $C$ of $B$ and that $F$ is
not in the interior of $C$. Let $B^{\prime}$ be the interior of the triangle
$x_{1}x_{2}x_{3}x_{1}$ in $B$, so $B^{\prime}$ is a subgraph of $B$. Since $G$
has no (18/7)-sparse sets of order at most two, there are at least two
vertices in $B^{\prime}$, and therefore $B^{\prime}$ has at least five
vertices. Thus, by Lemma 4.2, $B\in\\{B_{5,d},B_{6,g},B_{6,h},B_{7,b}\\}$ and
$(i)$ holds. Note that $B^{\prime}\in\\{B_{5,d},B_{6,g},B_{6,i}\\}$, up to
redrawing.

We claim that $|F|=4$. Since $B^{\prime}\in\\{B_{5,d},B_{6,g},B_{6,i}\\}$, by
checking cases, there is a length $i$ $x_{1}$-$x_{3}$ path $P_{i}$ in
$B^{\prime}$ for each $i\in[4]$. Then $|F|\notin\\{5,6\\}$, or else
$(F-x_{2})\cup P_{i}$ with $i\in\\{3,4\\}$ is a $C_{7}$ in $G$. Therefore
$|F|=4$.

Let $w$ be the vertex in $V(F)\setminus\\{x_{1},x_{2},x_{3}\\}$. We see that
$(ii)$ holds. If $wx_{1}$ or $wx_{3}$ is in a facial cycle of length less than
eight other than $F$, then such a facial cycle contains an $x_{1}$-$x_{3}$
path of length $\ell\in\\{3,4,5,6\\}$ that is internally disjoint from
$B^{\prime}$. The concatenation of this path with a length $(7-\ell)$
$x_{1}$-$x_{3}$ path of $B^{\prime}$ forms a $C_{7}$ in $G$, a contradiction.
Therefore $wx_{1}$ and $wx_{3}$ are trivial triangular-blocks of $G$ that are
incident with exactly one face of $G$ with length less than eight and $(iii)$
holds. ∎

##  5 Large Triangular-Blocks

Now that we have a complete characterization of possible triangular-blocks in
a $C_{7}$-free plane graph, we proceed by estimating

$g(B)=24f(B)-17e(B)+6n(B)$

for each possible triangular-block $B$. In this section we analyze the
possible triangular-blocks with at least six vertices for a graph
$G\in\mathcal{P}_{n}$. We first consider chordless near triangulations, and
then divide the remaining cases into three groups based on the length of the
outer cycle.

######  Lemma 5.1.

Let $G\in\mathcal{P}_{n}$ with $n\geq 7$, and let $B$ be a triangular-block of
$G$. If $B$ is a $6$-vertex near triangulation whose outer cycle has no chord
and whose outer face is its only hole, then $g(B)\leq 0$.

###### Proof.

Let $C$ be the outer cycle of $B$; this is the only possible non-triangle
facial cycle of $B$. Since $C$ has a chord, $|C|\leq 5$. It follows from
Lemmas 3.2 and 3.1 that for any distinct $x,y\in V(C)$, there is an $x$-$y$
path in $B$ of length $l$ for each $l$ between $d_{B}(x,y)$ (at most 2) and
$|B|-2=4$. Thus, to avoid $C_{7}$, each petal $F$ of $B$ has length at least
$8$ and, hence, the refinement of each petal has length at least $8$.

Note that at least two vertices on $C$ are junction vertices since $G$ is
$2$-connected, and for each junction vertex $v$ we have $n(v)\leq 1/2$.
Moreover, from Euler’s formula, we have $|E(B)|=15-|C|$ and $|F(B)|=11-|C|$.

If $|C|=4$, then

$g(B)\leq 24(6+4/8)-17\cdot 11+6(4+2/2)=-1;$

and if $|C|=5$, then

$g(B)\leq 24(5+5/8)-17\cdot 10+6(4+2/2)=-5.$

Thus we may assume that $B$ is a triangulation. If all vertices of $C$ are
junction vertices of $B$ then

$g(B)\leq 24(7+3/8)-17\cdot 12+6(3+3/2)=0.$

So assume that only two vertices of $C$ are junction vertices of $B$. Then $B$
has a bad cherry $x_{1}x_{2}x_{3}$ on a facial cycle $F$ of $B$ such that
$x_{1}x_{2},x_{2}x_{3}\in E(F)$. Thus,

$g(B)\leq 24(7+1/8+1/8)-17\cdot 12+6(4+2/2)=0,$

as desired. ∎

We next consider $6$-vertex and 7-vertex triangular-blocks whose outer cycle
has length 4 and a chord.

######  Lemma 5.2.

Let $G\in\mathcal{P}_{n}$ with $n\geq 7$, and let $B$ be a triangular-block of
$G$ with no triangular holes and at most one hole. If
$B\in\\{B_{6,g},B_{6,h},B_{6,i},B_{7,b}\\}$, then $g(B)<0$.

###### Proof.

We may assume that $G$ is drawn in the plane such that the outer face of $B$
is its hole. Let $C$ be the outer cycle of $B$. Let $x$ and $y$ be the ends of
the unique chord of $C$, and let $a$ and $b$ be the other two vertices on the
outer cycle of $B$, where $d_{B}(a)=2$ if $B\neq B_{6,i}$. If $B=B_{7,b}$, let
$c$ be the interior degree 2 vertex of $B$. Note that when $|B|=6$ then
$|E(B)|=11$ and $|F(B)|=7$, and when $|B|=7$ then $|E(B)|=13$ and $|F(B)|=8$.

Suppose for each petal $F$ of $B$, $|F|\geq 8$. Since $B$ has at least two
junction vertices, if $|B|=6$ then

$g(B)\leq 24(6+4/8)-17\cdot 11+6(4+2/2)=-1,$

and if $|B|=7$ then

$g(B)\leq 24(7+4/8)-17\cdot 13+6(5+2/2)=-5$

as desired.

Thus, we may assume that there is some petal $F$ of $B$ with $|F|<8$. We now
show that $|F|=4$ and $F=xbytx$ for some $t\notin V(B)$. To see this, let $P$
be a subpath of $F$ that is also a $B$-path, and let $v$ and $w$ be the ends
of $P$ in $B$. By Lemmas 3.1 and 3.2 (applied to $B-c$ if $B=B_{7,b}$), we see
that $B$ and $B-c$ have $v$-$w$ paths of any length between $d_{B}(v,w)$ and
$5$, unless $B=B_{6,i}$ and $\\{v,w\\}=\\{x,y\\}$. Thus, since $G$ is
$C_{7}$-free, $P=ab$, or $P=xty$ where $t\in V(F)\setminus V(B)$. This in
particular implies that $F$ cannot contain two such $B$-paths. Thus, $F\cap B$
is $xby$ or $yax$. Then $B\neq B_{6,i}$ or else $G$ has an (18/7)-sparse set.
Hence, $|F|=4$ and $F=xbytx$ as $a$ is a junction vertex (since $\\{a\\}$ is
not an (18/7)-sparse set).

Note that $F$ is the unique petal of $B$ with length less than eight, $b$ is a
not a junction vertex, and $xby$ is a bad cherry (thus $f_{F}(B)=1/3$).
Therefore, if $B\in\\{B_{6,g},B_{6,h}\\}$, we have

$g(B)\leq 24(6+2/8+1/3)-17\cdot 11+6(3+3/2)=-2,$

and if $B=B_{7,b}$ we have

$g(B)\leq 24(7+2/8+1/3)-17\cdot 13+6(4+3/2)=-6,$

as desired. ∎

To deal with other 6-vertex and 7-vertex triangular-blocks, we need a
technical lemma.

######  Lemma 5.3.

Let $G\in\mathcal{P}_{n}$ with $n\geq 7$ and let $B$ be a triangular-block of
$G$ with no triangular holes and
$B\in\\{B_{6,a},B_{6,b},B_{6,c},B_{6,d},B_{6,e},B_{6,f},B_{7,a}\\}$. Let $C$
be the outer cycle of $B$, $x_{1}x_{2}x_{3}$ be a subpath of $C$, and let
$F_{1},F_{2}$ be the petals of $B$ containing $x_{1}x_{2},x_{2}x_{3}$,
respectively. Suppose $G$ has a $B$-path $P$ between $x_{1}$ and $x_{3}$ of
length at most 2. Then $|F_{i}|\geq 8$ for $i=1,2$, unless

  * •

$B=B_{6,a}$ with $x_{1},x_{3}$ corresponding to $x,y$ as in Figure 1 and
$F_{1}=F_{2}$ is a 4-cycle, or

  * •

$B=B_{6,d}$ with $x_{1},x_{2}$ corresponding to $x,y$ as in Figure 1 and
$|F_{1}|\geq 8$.

###### Proof.

First, suppose $F_{1}\neq F_{2}$. Then, because of $P$ we see that each
$F_{i}$ contains an $x_{s_{i}}$-$x_{s_{i}+1}$ $B$-path for some $s_{i}\in[2]$.
If $B\neq B_{6,d}$, then Lemmas 3.1 and 3.2 imply that for all
$t\in\\{2,3,4,5\\}$, $B$ has an $x_{s_{i}}$-$x_{s_{i}+1}$ path of length $t$.
Thus, since $G$ is $C_{7}$-free, $|F_{i}|\geq 8$ for $i=1,2$. If $B=B_{6,d}$,
then by checking cases we see that for all $t\in[4]$, $B$ has an
$x_{s_{i}}$-$x_{s_{i}+1}$ path of length $t$. Since $|F_{i}|\geq 4$ (as $B$ is
a triangular-block), if $|F_{i}|\leq 6$ then by case analysis $B\cup F_{i}\cup
P$ contains a $C_{7}$ unless $x_{1},x_{2}$ correspond to $x,y$ as in Figure 1,
$|F_{2}|=4$, and $x_{2}x_{3}x_{1}\subseteq F_{2}$. Hence, $|F_{1}|\geq 8$.

So we may assume $F_{1}=F_{2}$. Again, because of the path $P$ and planarity,
$F_{1}\cap C=x_{1}x_{2}x_{3}$. So $|F_{1}|\geq 4$ as $B$ is a triangular-
block.

Suppose $B$ has an $x_{1}$-$x_{3}$ Hamiltonian path. Then by, Lemma 3.1, $B$
has an $x_{1}$-$x_{3}$ path of length $\ell$ for every $\ell$ between $2$ and
$5$. Therefore, $|F_{1}|\geq 8$ to avoid a $C_{7}$ in $G$.

Now assume $B$ has no $x_{1}$-$x_{3}$ Hamiltonian path. Then by Lemma 3.2,
$B=B_{6,a}$ with $x_{1},x_{3}$ corresponding to $x,y$ in Figure 1. Now $B$ has
an $x_{1}$-$x_{3}$ path of any length between 2 and 4. So if $|F_{1}|<8$ then
$|F_{1}|=4$. ∎

We next consider $6$-vertex triangular-blocks with five vertices on the outer
cycle.

######  Lemma 5.4.

Let $G\in\mathcal{P}_{n}$ with $n\geq 7$, and let $B$ be a triangular-block of
$G$ with no triangular hole. If $B\in\\{B_{6,d},B_{6,e},B_{6,f}\\}$, then
$g(B)<0$.

###### Proof.

By Lemma 4.3, each petal of $B$ with length at most six is equal to its
refinement. We may assume that $B$ is drawn as shown in Figure 4. Let $C$ be
the outer cycle of $B$, so $|C|=5$. Since no triangular face of $B$ is a hole,
all junction vertices of $B$ are contained in $C$ and there are at least two
(as $G$ is 2-connected) and must include all degree 2 vertices of $B$ (to
avoid an (18/7)-sparse set of order 1).

In fact, $C$ has at least three junction vertices of $B$. For, otherwise, let
$S$ be obtained from $V(B)$ by removing the junction vertices of $B$ (so
$|S|=4$). Then one can check that $S$ is an (18/7)-sparse set, a
contradiction.

If there are no $B$-paths of length at most 2, then each petal of $B$ has
length at least 8, and so

$g(B)\leq 24(5+5/8)-7\cdot 10+(3+3/2)<0.$

If there are two $B$-paths of length at most 2 that have different sets of
ends on $C$, then by Lemma 5.3, at least three petals of $B$ have length at
least 8; so

$g(B)\leq 24(5+3/8+2/4)-17\cdot 10+6(3+3/2)=-2.$

So we may assume that all $B$-paths of length at most 2 in $G$ have the same
ends on $B$, say $x$ and $y$, and that there is a petal $F$ of $B$ with
$|F|<8$. Then $F\cap B$ is a path of length 2 or 3, or else $G$ contains a
$C_{7}$ by Lemma 3.2 and Lemma 3.1. So by Lemma 5.3, $|F|=4$ and $F$ contains
a $B$-path of length 2 between $x$ and $y$, call it $P$. If $xy\notin E(B)$
then $B$ has an $x$-$y$ Hamiltonian path (by Lemma 3.2), together with $P$,
gives a $C_{7}$, a contradiction. So $xy\in E(B)$. But then $G$ has an
(18/7)-sparse set consisting of 1 or 2 vertices, a contradiction. ∎

Finally, we consider triangular-blocks with six vertices on the outer cycle.

######  Lemma 5.5.

Let $G\in\mathcal{P}_{n}$ with $n\geq 7$, and let $B$ be a triangular-block of
$G$ with no triangular hole. If $B\in\\{B_{6,a},B_{6,b},B_{6,c},B_{7,a}\\}$,
then $g(B)\leq 0$.

###### Proof.

By Lemma 4.3, each petal of $B$ with length at most six is equal to its
refinement. We may assume that $B$ is drawn as shown in Figure 4 or Figure 5.
Let $C$ be the outer cycle of $B$, so $|C|=6$. Note that every degree 2 vertex
in $B$ must be a junction vertex, to avoid an (18/7)-sparse set of order 1.
Thus, if $B$ has two junction vertices then $B\in\\{B_{6,a},B_{6,b}\\}$; but
then $\\{v\in V(B):d_{B}(v)\geq 3\\}$ is an (18/7)-sparse set in $G$, a
contradiction. So $B$ has at least three junction vertices.

If $B\neq B_{7,a}$ (so $|B|=6$, $|F(B)|=5$, and $|E(B)|=9$) and at least two
edges of $C$ are in petals of $B$ of length at least 8, then

$\displaystyle g(B)\leq 24(4+2/8+4/4)-17\cdot 9+6(3+3/2)=0.$ (1)

If $B=B_{7,a}$ (so $|B|=7$, $|F(B)|=7$, and $|E(B)|=12$) and at least three
edges of $C$ are in petals of $B$ of length at least 8, then

$\displaystyle g(B)\leq 24(6+3/8+3/4)-17\cdot 12+6(4+3/2)=0.$ (2)

Thus, we may assume that at most one edge (if $|B|=6$) or two edges (if
$|B|=7$) of $C$ are in petals of $B$ of length at least 8. Let $\mathcal{P}$
be the collection of $B$-paths of $G$ with at most two edges. Lemmas 3.1 and
3.2 imply that for each petal $F$ of $B$ with $|F|<8$, $F$ contains a path in
$\mathcal{P}$. We consider three cases.

First suppose that $B=B_{6,a}$. Let $v$ be a degree 2 vertex of $B$. Suppose
that $v$ is in a petal $F$ with $|F|<8$. Since $G$ has no degree 2 vertices,
$F$ contains a path $P$ in $\mathcal{P}$ with $v$ as an end. Since $v$ is not
the end of a chord of $C$ and $G$ contains no $C_{7}$, it follows from Lemma
3.2 that $P$ consists of a single edge. By Lemma 5.3 and (1), the other end of
$P$ is at distance three from $v$ on $C$. But then applying the same reasoning
to the other degree 2 vertex $u$ of $B$ shows that at least two edges of $C$
are each contained in a petal of length at least 8, and so (1) implies that
$g(B)\leq 0$.

Next suppose that $B\in\\{B_{6,b},B_{6,c}\\}$. Then by Lemma 5.3 and (1) we
may assume that the ends of each $P\in\mathcal{P}$ are at distance three on
$C$. This implies that each petal of $B$ with $|F|<8$ contains exactly one
path in $\mathcal{P}$ as a subpath. It is straightforward to check that $G$
has an (18/7)-sparse set unless $B=B_{6,b}$ and the ends of each
$P\in\mathcal{P}$ are the degree 2 vertices of $B$. Since the degree 2
vertices of $B$ are not the ends of a chord of $C$, it follows that each
$P\in\mathcal{P}$ consists of a single edge to avoid a $C_{7}$ in $B\cup P$,
and so $|\mathcal{P}|=1$. Therefore there is a unique petal $F$ of $B$ with
$|F|<8$. Since only three edges of $C$ are contained in $F$, there are three
edges of $C$ contained in petals of length at least 8. Then (1) implies that
$g(B)\leq 0$.

Finally, suppose that $B=B_{7,a}$. If there is a path $P$ in $\mathcal{P}$
with both ends having degree 2 in $B$ then $B\cup P$ contains $C_{7}$, a
contradiction. By Lemma 5.3 and (2) there is at most one path in $\mathcal{P}$
with neither end having degree 2 in $B$, and clearly there is at most one path
in $\mathcal{P}$ with exactly one end having degree 2 in $B$. So $\mathcal{P}$
contains at most two paths and, since $G$ has no degree 2 vertex, it follows
that there is a unique petal of $B$ with $|F|<8$ (and $F$ contains both paths
in $\mathcal{P}$). Since $F$ contains at most three edges of $C$, at least
three edges of $C$ are each contained in a petal of $B$ of length at least 8;
so (2) implies that $g(B)\leq 0$. ∎

##  6 Five-vertex triangular-blocks

In this section we analyze the possible $5$-vertex triangular-blocks of a
graph $G\in\mathcal{P}_{n}$.

######  Lemma 6.1.

Let $G\in\mathcal{P}_{n}$ with $n\geq 7$, and let $B$ be a triangular-block of
$G$, and assume that $G$ is drawn in the plane such that $B=B_{5,a}$ is drawn
as in Figure 3. Then $g(B)\leq 0$.

###### Proof.

By Lemma 4.3, each petal of $B$ with length at most six is equal to its
refinement. Lemma 2.3 shows that no triangular face of $B$ is a hole. Let
$C=abcdea$ be the outer cycle of $B$ with $d_{B}(a)=4$. Note that $B$ has at
least three junction vertices, or else $\\{b\\}$ or $\\{e\\}$ or $\\{c,d\\}$
would be an (18/7)-sparse set in $G$.

If at least two edges of $C$ are contained in petals of $B$ of length at least
8, then

$g(B)\leq 24(3+2/8+3/4)-17\cdot 7+6(2+3/2)=-2.$

So we may assume that at most one edge of $C$ is contained in a petal of $B$
of length at least 8. This implies, up to relabeling vertices, that the edges
$ab$ and $bc$ are not in a petal of length at least 8. Let $F_{1}$ and $F_{2}$
be petals of $B$ that contain $ab$ and $bc$, respectively.

Suppose $F_{1}$ and $F_{2}$ are both leaky. It is straightforward to check
that there is a pair $(P_{1},P_{2})$ of length 2 $B$-paths where
$P_{i}\subseteq F_{i}$, the ends of $P_{i}$ are not $\\{a,c\\}$ or
$\\{a,d\\}$, and $P_{1}$ and $P_{2}$ have distinct sets of ends. But then
$B\cup P_{1}\cup P_{2}$ contains $C_{7}$, a contradiction. So either $F_{1}$
or $F_{2}$ is not leaky.

We claim that if $F_{1}$ is not leaky then $F_{1}\cap C=eab$ and if $F_{2}$ is
not leaky then $F_{2}\cap C=bcd$. Suppose $F_{1}$ is not leaky. First,
$F_{1}\cap C$ does not contain $deab$ or $abc$, as otherwise $\\{e\\}$ or
$\\{b\\}$ would be an (18/7)-sparse set in $G$. Now suppose $F_{1}\cap C=ab$.
Then since $B$ has an $a$-$b$ path of every length between 1 and $4$ and
$|F|<8$, $G$ has a $C_{7}$, a contradiction. Therefore $F_{1}\cap C=eab$, and
similar argument shows that if $F_{2}$ is not leaky then $F_{2}\cap C=bcd$.

Suppose $F_{1}$ and $F_{2}$ are both non-leaky. Then by the above claim,
$|F_{1}|=|F_{2}|=4$ (to avoid $C_{7}$ in $G$). Let $F_{1}=veabv$ and
$F_{2}=wbcdw$. If $v\neq w$, we see that $B\cup F_{1}\cup F_{2}$ contains a
$C_{7}$, a contradiction. So $v=w$. But then $\\{b,c\\}$ is an (18/7)-sparse
set in $G$, a contradiction.

We may thus assume that $F_{1}$ is not leaky and $F_{2}$ is leaky, as the same
argument applies to the case when $F_{1}$ is leaky and $F_{2}$ is not leaky.
Hence, $F_{1}\cap C=eab$ and $|F_{1}|=4$.

We claim that $F_{2}\cap C$ consists of $bc$ and $e$. For, otherwise,
$F_{2}\cap C$ contains a $B$-path $P$ between $c$ and $d$ which is also
disjoint from $F_{1}$ (by planarity). Note that $P$ has length between 2 and 5
and that $B\cup F_{1}$ has $c$-$d$ paths of every length between 1 and 5.
Hence, $B\cup F_{1}\cup P$ contains $C_{7}$, a contradiction.

The same argument in the above paragraph shows that $ce$ is an edge of
$F_{2}$. Moreover, the $b$-$e$ subpath of $F_{2}-c$ has length 2, to avoid
forming a $C_{7}$ with a $b$-$e$ path in $B\cup F_{1}$. Let $F_{1}=veabv$ and
$F_{2}=wbcew$. If $v=w$ then $d_{G}(v)=2$ and $\\{v\\}$ is an (18/7)-sparse
set in $G$, a contradiction. So $v\neq w$.

Now the petals of $B$ containing $cd$ and $de$ are distinct. For, otherwise,
the petal containing $cde$ has length between 4 and 6, which, together with a
$c$-$e$ path in $B\cup P$ forms a $C_{7}$, a contradiction. Moreover, the
petals containing $cd$ or $de$ each contains a $(B\cup F_{1})$-path of length
at least 3 with both ends in $\\{c,d,e\\}$. But then one of these paths has
length at most 6, which forms a $C_{7}$ with a path in $B$, a contradiction. ∎

######  Lemma 6.2.

Let $G\in\mathcal{P}_{n}$ with $n\geq 7$ and let $B$ be a triangular-block of
$G$. Suppose that $G$ is drawn in the plane such that $B=B_{5,d}$ is drawn as
in Figure 3 and its only hole is its outer face. Then $g(B)\leq 0$.

###### Proof.

First, we observe that every $B$-path in $G$ has length $\ell$ with $\ell=2$
or $\ell\geq 7$. For, otherwise, suppose $P$ is a $B$-path in $G$ of length
$\ell$ with $3\leq\ell\leq 6$. Note that $B$ contains a path $Q$ of length
$7-\ell$ between the ends of $P$. Now $P\cup Q$ is a $C_{7}$ in $G$, a
contradiction.

Let $uvwu$ be the outer cycle of $B$. (Note that we do not specify the
vertices $u,v,w$.) Thus, all junction vertices of $B$ are contained in
$\\{u,v,w\\}$ and, since $G$ is 2-connected, at least two of $\\{u,v,w\\}$ are
junction vertices of $B$. Hence, if each edge of $uvwu$ is in a petal of $B$
of length at least 8, then

$g(B)\leq 24(5+3/8)-17\cdot 9+6(3+2/2)=0,$

so we may assume that there is a petal $F$ of $B$ with $|F|<8$.

We claim that $|F|=4$ and $F$ has a bad cherry (so $f_{F}(B)=1/3$). To see
this, let $P$ be a longest $B$-path contained in $F$. By the observation
above, $P$ has length 2 (as $|F|<8$). Since $B$ is a triangular-block, $P$ and
two edges of $uvwu$ bounds the face $F$. So $|F|=4$, and $F\cap B$ is a bad
cherry. Without loss of generality, assume that $F\cap B=vwu$.

We next consider the petal $F_{1}$ of $B$ containing $uv$. Note that
$F_{1}-uv$ is a $B$-path, because $w$ is in the interior of $F$. Hence, since
$|F_{1}|\geq 4$, $F_{1}-uv$ has length at least 7 (by the above observation).
So $|F_{1}|\geq 8$ (and $f_{F_{1}}(B)\leq 1/8$).

We now show that $u$ and $v$ are each contained in at least three triangular-
blocks of $G$. For, suppose, without loss of generality, that $v$ is in
exactly two triangular-blocks of $G$. Let $x$ be the vertex in
$F-\\{u,v,w\\}$. If $N_{G}(v)\subseteq V(B\cup F)$, then
$V(B)\setminus\\{u\\}$ is an (18/7)-sparse set in $G$, a contradiction. So $v$
has a neighbor outside $B\cup F$, say $y$. Then $vy$ and $vx$ are in some
triangular-block $B^{\prime}$ of $G$. One can check that $B^{\prime}$ or
$G[V(B^{\prime})\cup\\{u\\}]$ contains a $v$-$u$ path of length of 3 or 4,
which together with a $u$-$v$ path in $B$ forms a $C_{7}$ in $G$, a
contradiction. Therefore,

$g(B)\leq 24(5+1/8+1/3)-17\cdot 9+6(3+2/3)=0,$

as desired. ∎

$c$$b$$a$$d$$v$$u$ | $c$$b$$a$$d$$v$$u$
---|---
Figure 6: The two exceptional flowers.

######  Lemma 6.3.

Let $G\in\mathcal{P}_{n}$ with $n\geq 7$ and let $B$ be a triangular-block of
$G$. Suppose that $G$ is drawn in the plane such that
$B\in\\{B_{5,b},B_{5,c}\\}$ is drawn as in Figure 3. Then $g(B)\leq 0$ unless
the flower of $B$ is one of the two graphs shown in Figure 6, up to redrawings
that preserve facial cycles.

###### Proof.

By Lemma 4.3, each petal of $B$ with length at most six is equal to its
refinement. Lemma 2.3 shows that the only hole of $B$ is its outer face. Let
$C=abcda$ be the outer cycle of $B$, with $d_{B}(d)=2$ if $B=B_{5,c}$. Note
that no petal of $B$ has a bad cherry, as otherwise it is easy to see that
$B=B_{5,c}$ and one or two vertices of $B$ would form an (18/7)-sparse set in
$G$. Since $G$ is 2-connected, $B$ has at least 2 junction vertices. Thus, if
each edge of $C$ is in a petal of $B$ of length at least 8, then

$g(B)\leq 24(4+4/8)-17\cdot 8+6(3+2/2)=-4.$

So we may assume that there is a petal $F$ of $B$ with $|F|<8$.

Thus, $F$ contains a $B$-path $P$ of length between 2 and 5. To avoid forming
$C_{7}$ with a path in $B$, $P$ has length 2 if the ends of $P$ do not induce
a chord of $C$, and $P$ has length 2 or 3 otherwise.

Suppose that we may choose $P$ so that the ends of $P$ are adjacent on $C$.
Then $P$ has length 2 to avoid forming a $C_{7}$ with $B$, and, since $B$ is a
triangular-block, $F$ is a leaky petal. Therefore, $F$ contains a second
$B$-path $P^{\prime}$ which does not have the same two ends as $P$, and hence
$B$ has at least three junction vertices. Note that $B\cup P$ is a near
triangulation on 6 vertices, and also note by the above paragraph that
$P^{\prime}$ has length at most 3. It is straightforward to check that
$P^{\prime}$ has length 1, or else $B\cup P^{\prime}$ or $B\cup P\cup
P^{\prime}$ would contain $C_{7}$. Thus, if $B=B_{5,c}$ then $P^{\prime}\neq
ac$. Hence, without loss of generality we may assume that $P^{\prime}=bd$, and
that the triangle $abda$ separates $B$ from some vertex of $G$. Then the petal
of $B$ containing $ab$ either contains an $a$-$b$ path of length at least 7 or
a $b$-$d$ path of length at least 6 to avoid forming a $C_{7}$ with $B$, and
in either case has length at least 8. Similarly, the petal of $B$ containing
$ad$ has length at least 8. Therefore

$g(B)\leq 24(4+2/8+2/4)-17\cdot 8+6(2+3/2)=-1,$

as desired.

So we may assume that $F$ contains no $B$-path with length between 2 and 5
whose ends are adjacent on $C$. Then $F$ is not a leaky petal. If $B=B_{5,c}$
and $P$ is an $a$-$c$ path, then $G$ has a sparse set consisting of 1 or 2
vertices from $V(B)\setminus\\{a,c\\}$, a contradiction. So we may assume
without loss of generality that $P$ is a $b$-$d$ path (so $P$ has length 2 to
avoid forming a $C_{7}$ with $B$) and that $F$ is the cycle $bcdvb$, where $v$
is the internal vertex of $P$.

If $B$ has three junction vertices, then the petal $F_{1}$ of $B$ containing
$ab$ also contains a $B$-path of length at least 2 with ends $a$ and $b$ or
$a$ and $d$. Since such a path has length at least 7 (to avoid forming a
$C_{7}$ with $B$), $|F_{1}|\geq 8$. Similarly, the petal of $B$ containing
$ad$ has length at least 8. Then

$g(B)\leq 24(4+2/8+2/4)-17\cdot 8+6(2+3/2)=-1.$

So we may assume that $B$ has exactly two junction vertices, namely $b$ and
$d$. Then the petal $F_{1}$ of $B$ containing the path $dab$ is the union of
$dab$ and a $B$-path $Q$ in $G$ between $d$ and $b$. As with $P$ and $F$, $Q$
has length 2 or at least 6 to avoid creating $C_{7}$ with $B$. If $Q$ has
length 2, then $v\notin V(Q)$ and the flower of $B$ is shown in Figure 6.

So assume $Q$ has length at least 6. Then $|F_{1}|\geq 8$. If $b$ and $d$ are
each in at least three triangular-blocks of $G$ then

$g(B)\leq 24(4+2/8+2/4)-17\cdot 8+6(3+2/3)=0.$

So assume by symmetry that $b$ is in exactly two triangular-blocks of $G$. If
$N_{G}(b)\subseteq V(B\cup P)$ then $V(B-d)$ is an (18/7)-sparse set in $G$, a
contradiction. So $b$ has a neighbor $z$ outside $B\cup P$. Then $bv$ and $bz$
are in the same triangular-block $B^{\prime}$ of $G$. Now $B^{\prime}$
contains a $b$-$v$ path of length between 2 and 6, which is also a $(B\cup
P)$-path. However, this path and a $b$-$v$ path in $B\cup P$ form a $C_{7}$ in
$G$, a contradiction. ∎

Finally, for the triangular-blocks with flower shown in Figure 6, we note that
each edge of its outer cycle is contained in a facial cycle of length at least
5, to avoid a $C_{7}$ in $G$. Thus, we have the following.

######  Lemma 6.4.

Let $G\in\mathcal{P}_{n}$ with $n\geq 7$. Let $B$ be a triangular-block of $G$
with flower shown in Figure 6, and let $e\in E(G)\setminus E(B)$ be in a petal
of $B$. Then $e$ is incident with exactly one face of $G$ of length less than
five. In particular, $e$ is a trivial triangular-block.

##  7 Small Triangular-Blocks

In this section we analyze the triangular-blocks with at most four vertices in
a graph $G\in\mathcal{P}_{n}$. We first consider trivial triangular-blocks.

######  Lemma 7.1.

Let $G\in\mathcal{P}_{n}$ with $n\geq 7$ and let $B$ be trivial triangular-
block of $G$. Then $g(B)\leq 0$.

###### Proof.

Let $x_{1}$ and $x_{2}$ be the two vertices of $B$, and let $F_{1}$ and
$F_{2}$ be the two petals of $B$. Note that $|F_{i}|\geq 4$ for each $i\in[2]$
since $B$ is a triangular-block. Each of $x_{1}$ and $x_{2}$ is in at least
two triangular-blocks, so $n(B)\leq\frac{1}{2}+\frac{1}{2}=1$.

We may assume that for each $i\in[2]$, $|F_{i}|=4$, $F_{i}$ equals its
refinement, and $x_{i}$ is contained in exactly two triangular-blocks of $G$
(including $B$). First, if the refinement of $F_{1}$ is not $F_{1}$ then Lemma
4.3 implies that $|F_{1}|\geq 8$ and $|F_{2}|\geq 4$, or $|F_{1}|=4$ and
$|F_{2}|\geq 8$; so

$g(B)\leq 24(1/8+1/4)-17+6(1/2+1/2)=-2.$

So we may assume that $F_{1}$ and $F_{2}$ are both equal to their refinements.
Next, if $|F_{1}|\geq 5$ or $|F_{2}|\geq 5$ then

$g(B)\leq 24(1/4+1/5)-17+6(1/2+1/2)=-1/5,$

so we may assume that $|F_{1}|=|F_{2}|=4$. Now assume $x_{1}$ or $x_{2}$ is in
at least three triangular-blocks of $G$. Then
$n(B)\leq\frac{1}{2}+\frac{1}{3}$ and again

$g(B)\leq 24(1/4+1/4)-17+6(1/2+1/3)=0.$

So both $x_{1}$ and $x_{2}$ are each contained in exactly 2 triangular-blocks.
Let $x_{3}$ and $x_{4}$ be the vertices of $F_{1}$ other than $x_{1}$ and
$x_{2}$, such that $F_{1}=x_{1}x_{2}x_{3}x_{4}x_{1}$.

Case 1\. $V(F_{1}\cap F_{2})=\\{x_{1},x_{2}\\}$.

Let $x_{5}$ and $x_{6}$ be the other two vertices of $F_{2}$, such that
$F_{2}=x_{1}x_{2}x_{5}x_{6}x_{1}$. Now $d_{G}(x_{i})\geq 4$ for some
$i\in[2]$, as $\\{x_{1},x_{2}\\}$ is not an (18/7)-sparse set. By symmetry,
assume $d_{G}(x_{2})\geq 4$. Consider the triangular-block $B^{\prime}$ of $G$
such that $B^{\prime}$ contains $x_{3}x_{2}x_{5}$, and let $F_{3}$ and $F_{5}$
be the facial triangles of $B^{\prime}$ containing $x_{2}x_{3}$ and
$x_{2}x_{5}$, respectively. If $F_{3}$ contains a third vertex in
$\\{x_{1},x_{2},x_{3},x_{4},x_{5},x_{6}\\}$, it must be $x_{6}$ to avoid an
(18/7)-sparse set of order 1. But then $F_{5}$ contains a vertex $v$ with
$v\notin\\{x_{1},x_{2},x_{3},x_{4},x_{5},x_{6}\\}$, and
$x_{2}vx_{5}x_{6}x_{1}x_{4}x_{3}x_{2}$ is a $C_{7}$ in $G$, a contradiction.

Case 2\. $V(F_{1}\cap F_{2})\neq\\{x_{1},x_{2}\\}$

Then $|V(F_{1}\cap F_{2})|=3$. Without loss of generality we may assume that
$x_{4}\in V(F_{2})$. Let $x_{5}$ be the fourth vertex of $F_{2}$; then
$F_{2}=x_{1}x_{2}x_{4}x_{5}x_{1}$. Note that $x_{4}x_{1}x_{5}x_{4}$ bounds a
triangular-block $B_{1}$ of $G$ since $x_{1}$ is in exactly 2 triangular-
blocks of $G$. Since $F_{2}$ is a facial cycle and $\\{x_{5}\\}$ cannot be a
sparse set in $G$, $|B_{1}|\geq 4$. Since $x_{1}x_{4}$ in an edge on the outer
cycle of $B_{1}$, Lemmas 3.2 and 3.1 imply that $B_{1}$ contains an
$x_{1}$-$x_{4}$ path $P$ of length 3. Note that the path $x_{3}x_{2}x_{4}$ is
contained in a triangular-block $B_{2}$ of $G$, and the facial triangle of $B$
containing $x_{2}x_{3}$ contains a vertex
$v\notin\\{x_{1},x_{2},x_{3},x_{4},x_{5}\\}$ as $\\{x_{3}\\}$ cannot be an
(18/7)-sparse set of $G$. But then $P\cup x_{1}x_{2}vx_{3}x_{4}$ is a $C_{7}$
in $G$, a contradiction. ∎

######  Lemma 7.2.

Let $G\in\mathcal{P}_{n}$ with $n\geq 7$ and let $B$ be a triangular-block of
$G$. If $B=B_{3}$ as in Figure 2, then $g(B)\leq 0$.

###### Proof.

By Lemma 4.3 and to avoid a $C_{7}$, each petal of $B$ with length at most six
is equal to its refinement. Note that each vertex of $B$ is a junction vertex,
since $G$ has no degree 2 vertex. Hence,

$g(B)\leq 24(1+3/4)-17\cdot 3+6(3/2)=0,$

as desired. ∎

######  Lemma 7.3.

Let $G\in\mathcal{P}_{n}$ with $n\geq 7$ and let $B$ be a triangular-block of
$G$. Suppose $G$ is drawn in the plane such that $B=B_{4,b}$ is drawn as in
Figure 2 with its outer face as its only hole. Then $g(B)\leq 0$.

###### Proof.

By Lemma 4.3, each petal of $B$ with length at most six is equal to its
refinement. Let $a,b,c$ be the vertices of the outer cycle of $B$, which are
all junction vertices (to avoid an (18/7)-sparse set consisting of two
adjacent vertices). If there is a petal of $B$ with length at least 8, then

$g(B)\leq 24(3+1/8+2/4)-17\cdot 6+6(1+3/2)=0.$

So we may assume that each petal of $B$ has length less than 8.

Suppose $B$ has a leaky petal, say $F_{1}$, and assume by symmetry that $bc\in
E(F_{1})$. Then $F_{1}$ is the union of $bc$, a $B$-path $P_{1}$ between $a$
and $b$, and a $B$-path $P_{2}$ between $a$ and $c$. Note that for each
$i\in[2]$, $P_{i}$ has length 2 (or else $B\cup P_{1}\cup P_{2}$ would contain
$C_{7}$), and let $v_{i}$ be the internal vertex of $P_{i}$. Now, the petal
$F_{2}$ of $B$ containing $ac$ contains a $B$-path $Q$ between $a$ and $c$.
Note that the length of $Q$ is between $3$ and $5$, and hence $Q\cup P_{1}\cup
B$ contains a $C_{7}$, a contradiction.

So we may assume that $B$ has no leaky petal. Since $a,b,c$ are all junction
vertices of $G$ and there is no $B$-path of length 4 or 5 in $G$ (to avoid
forming a $C_{7}$ with $B$), each petal of $B$ has length 4. Let
$F_{1},F_{2},F_{3}$ be the petals containing $ac,ab,bc$, respectively.

Let $x$ and $y$ be the vertices of $F_{1}$ that are not in $B$ so that
$F_{1}=axyca$. Then $F_{2}$ contains a vertex $z$ that is not in $B\cup F_{1}$
(to avoid an (18/7)-sparse set of order at most 2 in $G$) and such $z$ is
unique to avoid a $C_{7}$ in $B\cup F_{1}\cup F_{2}$. So $z$ has two neighbors
on $B\cup F_{1}$ that are in $F_{2}$: $a$ and $c$, or $a$ and $y$, or $b$ and
$x$. If these neighbors of $z$ are $b$ and $x$ then $B\cup F_{1}\cup F_{2}$
contains $C_{7}$, a contradiction. If the neighbors are $a$ and $c$ then $b$
is not a junction vertex, a contradiction. So the neighbors of $z$ are $a$ and
$y$, and then the fourth edge of $F_{2}$ is $by$ or $ay$.

By applying the same reasoning to the petals $F_{1}$ and $F_{3}$, we deduce
that $bx\in E(F_{3})$ or $cx\in E(F_{3})$, and this is a contradiction because
$b$ and $x$ are separated by the cycle $azyca$ or $ayca$. ∎

######  Lemma 7.4.

Let $G\in\mathcal{P}_{n}$ with $n\geq 7$ and let $B$ be a triangular-block of
$G$. Suppose $G$ is drawn in the plane such that $B=B_{4,a}$ is drawn as in
Figure 2 with its outer face as its only hole. Then $g(B)\leq 0$.

###### Proof.

By Lemma 4.3, each petal of $B$ with length at most six is equal to its
refinement. Lemma 2.3 shows that $B$ has no triangular hole. Let $C=abcda$ be
the outer cycle of $B$, with $a,c$ of degree 3 in $B$. Note that $b,d$ must be
junction vertices as $\\{b\\}$ and $\\{d\\}$ cannot be an (18/7)-sparse set.
If both $a$ and $c$ are junction vertices, then

$g(B)\leq 24(2+4/4)-17\cdot 5+6(4/2)=-1.$

So we may assume by symmetry that $c$ is not a junction vertex. Then $a$ is a
junction vertex (as $\\{a,c\\}$ is not an (18/7)-sparse set), and the path
$bcd$ is contained a petal of $B$, say $F_{1}$.

We may assume $|F_{1}|=4$, or else, $|F_{1}|\geq 5$ and

$g(B)\leq 24(2+2/4+2/5)-17\cdot 5+6(1+3/2)=-2/5.$

Then $F_{1}$ is not leaky. Let $F_{1}=bcdvb$, where $v\notin V(B)$.

Let $F_{2},F_{3}$ denote the petals of $B$ containing $ab,ad$, respectively.
Then $F_{2}\neq F_{3}$, or else $\\{a,c\\}$ would be an (18/7)-sparse set in
$G$. We may assume $|F_{2}|=4$; for otherwise, $|F_{2}|\geq 5$ and
$|F_{3}|\geq 5$, and

$g(B)\leq 24(2+2/4+2/5)-17\cdot 5+6(1+3/2)=-2/5.$

Note that $F_{2}$ contains a unique vertex, say $w$, not contained in $B\cup
F_{1}$, to avoid a $C_{7}$ in $B\cup F_{1}\cup F_{2}$. Let $e_{1},e_{2}$ be
the edges of $F_{2}-ab$ incident with $a,b$, respectively. Then
$e_{1},e_{2}\notin E(B\cup F_{1})$, or else $\\{a,c\\}$ or $\\{b,c\\}$ would
be an (18/7)-sparse set in $G$. Since $e_{1}$ and $e_{2}$ cannot both be
incident to $w$, either $e_{1}=av$ and $e_{2}=bw$, or $e_{1}=aw$ and
$e_{2}=bd$.

If $e_{1}=aw$ and $e_{2}=bd$ then $w$ is incident to $a$ and $d$. But then
$F_{3}$ consists of $ad$ and a $(B\cup F_{1})$-path between $a$ and $d$, which
has length at least 3 (as $B$ is a triangular-block) and forms a $C_{7}$ with
$B\cup F_{1}$, a contradiction.

So $e_{1}=av$ and $e_{2}=bw$, which implies that $F_{2}=abwva$. Since
$\\{c,d\\}$ is not an (18/7)-sparse set in $G$, $F_{3}$ contains a $(B\cup
F_{1}\cup F_{2})$-path between $a$ and $d$ or between $d$ and $v$. But then
$|F_{3}|\geq 8$ to avoid a $C_{7}$ in $B\cup F_{1}\cup F_{3}$ or $B\cup
F_{1}\cup F_{2}\cup F_{3}$, and so

$g(B)\leq 24(2+3/4+1/8)-17\cdot 5+6(1+3/2)=-1,$

as desired. ∎

##  8 The $2$-Connected Case

The lemmas in the previous sections combine to show the following.

######  Lemma 8.1.

Let $G\in\mathcal{P}_{n}$ with $n\geq 7$, and let $B$ be a triangular-block of
$G$ with only one hole, and no triangular hole unless $B$ is a triangulation.
Then $g(B)\leq 0$, with the exception of the two cases shown in Figure 6.

We next show that this is true even for triangular-blocks with more than one
hole.

######  Lemma 8.2.

Let $G\in\mathcal{P}_{n}$ with $n\geq 7$. If $B$ is a triangular-block of $G$
then $g(B)\leq 0$, with the exception of the two cases shown in Figure 6.

###### Proof.

We draw $G$ so that $B$ is drawn as shown in Figures 2 \- 5 and the outer face
of $B$ is a hole. If $B$ has no other holes, then the statement follows from
Lemma 8.1. So let $\mathcal{F}$ be the set of facial cycles of $B$ bounding a
hole other than the outer face of $B$. Note that each $F\in\mathcal{F}$
satisfies $|F|\leq 4$.

Let $G^{\prime}$ be obtained from $G$ by deleting all vertices and edges in
the interior of $F$ for all $F\in\mathcal{F}$. Let $e^{\prime}(B)$,
$n^{\prime}(B)$, $f^{\prime}(B)$, and $g^{\prime}(B)$ be the values of $e(B)$,
$n(B)$, $f(B)$, and $g(B)$ calculated with respect to $G^{\prime}$. By Lemma
8.1, we have $g^{\prime}(B)\leq 0$. Note that $e(B)=e^{\prime}(B)$, and
$n(B)\leq n^{\prime}(B)$ because for each vertex $v$ of $B$, the number of
triangular-blocks in $G$ containing $v$ is at least the number of triangular-
blocks in $G^{\prime}$ containing $v$. Also, each $F\in\mathcal{F}$
contributes $1$ towards $f^{\prime}(B)$ and at most $4/4$ towards $f(B)$,
because $|F|\leq 4$, and each petal of $B$ has length at least four since $B$
is a triangular-block. So $f(B)\leq f^{\prime}(B)$. Therefore, $g(B)\leq
g^{\prime}(B)\leq 0$. ∎

We can now combine Lemma 2.10 with Lemma 8.2 to show that Theorem 1.1 holds
for graphs in $\mathcal{P}_{n}$ with $n\geq 7$.

######  Theorem 8.3.

Let $G\in\mathcal{P}_{n}$ with $n\geq 7$. Then
$e(G)\leq\frac{18n}{7}-\frac{48}{7}$.

###### Proof.

Let $\mathcal{B}$ be the collection of triangular-blocks of $G$, and let
$\mathcal{B}_{1}\subseteq\mathcal{B}$ be the collection of all exceptional
triangular-blocks of $G$ with flower shown in Figure 6.

We now define a suitable partition $\mathcal{P}$ of $\mathcal{B}$. Let
$B\in\mathcal{B}$. If $B\in\mathcal{B}_{1}$, then (by Lemma 6.4) let
$e_{1},e_{2},e_{3},e_{4}$ be the four trivial blocks in $G$ that are contained
in the flower of $B$, and let $\\{B,e_{1},e_{2},e_{3},e_{4}\\}\in\mathcal{P}$.
If $B\notin\mathcal{B}_{1}$ and is not a trivial block in $G$ contained in the
flower of a triangular-block in $\mathcal{B}_{1}$, let
$\\{B\\}\in\mathcal{P}$. To show that $\mathcal{P}$ is a partition of
$\mathcal{B}$, it suffices to show that there is no trivial triangular-block
$e$ that is in the flowers of two blocks in $\mathcal{B}_{1}$. This follows
from Lemma 6.4, because $e$ would be incident with two faces of length four.

By Lemma 2.10, it suffices to show that each set
$\mathcal{B}^{\prime}\in\mathcal{P}$ satisfies
$\sum_{B\in\mathcal{B}^{\prime}}g(B)\leq 0$. If $\mathcal{B}^{\prime}=\\{B\\}$
for some triangular-block $B$ in $G$, then $B$ is not exceptional and it
follows from Lemma 8.2 that $\sum_{B\in\mathcal{B}^{\prime}}g(B)=g(B)\leq 0$.
Otherwise $\mathcal{B}^{\prime}=\\{B,e_{1},e_{2},e_{3},e_{4}\\}$ for some
exceptional block $B$ and the four trivial blocks $e_{1},e_{2},e_{3},e_{4}$ in
the flower of $B$. For each $i\in[4]$, the edge $e_{i}$ is incident with a
face of length at least five by Lemma 6.4, and both its ends are in at least
three triangular-blocks, and so

$g(e_{i})\leq 24(1/4+1/5)-17+6(2/3)=-11/5.$

Since

$g(B)\leq 24(4+4/4)-17\cdot 8+6(3+2/2)=8$

using Lemma 4.3, we calculate that $\sum_{B\in\mathcal{B}^{\prime}}g(B)\leq
8-4(11/5)=-4/5<0$. Therefore each $\mathcal{B}^{\prime}\in\mathcal{P}$
satisfies $\sum_{B\in\mathcal{B}^{\prime}}g(B)\leq 0$, and Lemma 2.10 implies
that $e(G)\leq\frac{18n}{7}-\frac{48}{7}$. ∎

##  9 The Main Proof

We now obtain Theorem 1.1 from Theorem 1.2 by considering small separations
and sparse sets.

###### Proof of Theorem 1.1.

Let $\mathcal{G}_{0}$ be the class consisting of all planar graphs with at
most six vertices or with a planar drawing in $\mathcal{P}_{n}$ for some
$n\geq 7$. For each positive integer $i$, let $\mathcal{G}_{i}$ be the union
of $\mathcal{G}_{i-1}$ and the class of $C_{7}$-free planar graphs obtained
from any of the following operations:

  1. (1)

Add a set $S$ of vertices, and edges with at least one vertex in $S$ to a
graph in $\mathcal{G}_{i-1}$ such that $|S|\leq 4$ and $S$ is an (18/7)-sparse
set in the new graph.

  2. (2)

Take the disjoint union of two graphs in $\mathcal{G}_{i-1}$.

  3. (3)

Glue two graphs in $\mathcal{G}_{i-1}$ together at a vertex.

Let $\mathcal{G}=\cup_{i\geq 0}\mathcal{G}_{i}$, and note that $\mathcal{G}$
is precisely the class of $C_{7}$-free planar graphs. We will show that
operations (1)-(3) can only decrease density.

######  9.0.1.

Let $G_{1}$ be an $n_{1}$-vertex $C_{7}$-free planar graph with
$e(G_{1})\leq\frac{18n_{1}}{7}-c_{1}$ for some constant $c_{1}$. If $G$ is an
$n$-vertex $C_{7}$-free planar graph obtained from $G_{1}$ by operation $(1)$
by adding an (18/7)-sparse set $S$, then
$e(G)\leq\frac{18n}{7}-c_{1}-\left(\frac{18|S|}{7}-\lfloor\frac{18|S|}{7}\rfloor\right)$.

###### Proof.

Note that $n=n_{1}+|S|$ and

$e(G)\leq\frac{18n_{1}}{7}-c_{1}+\Bigl{\lfloor}\frac{18|S|}{7}\Bigr{\rfloor}=\frac{18n}{7}-c_{1}-\left(\frac{18|S|}{7}-\Bigl{\lfloor}\frac{18|S|}{7}\Bigr{\rfloor}\right).$

∎

Note that when $|S|\in[2]$ this gives a saving of $1/7$, and when
$|S|\in\\{3,4\\}$ this gives a saving of $2/7$. We perform a similar
calculation for operations (2) and (3).

######  9.0.2.

For each $i\in[2]$, let $G_{i}$ be an $n_{i}$-vertex $C_{7}$-free planar graph
with $e(G_{i})\leq\frac{18n_{i}}{7}-c_{i}$ for a constant $c_{i}$. If $G$ is
an $n$-vertex $C_{7}$-free planar graph obtained by applying operation $(2)$
or $(3)$ to $G_{1}$ and $G_{2}$, then
$e(G)\leq\frac{18n}{7}-c_{1}-c_{2}+\frac{18}{7}$. Moreover, if $(3)$ applies,
then $e(G)\leq\frac{18n}{7}-c_{1}-c_{2}$.

###### Proof.

We have

$\displaystyle e(G)$ $\displaystyle=e(G_{1})+e(G_{2})$
$\displaystyle\leq\frac{18n_{1}}{7}-c_{1}+\frac{18n_{2}}{7}-c_{2}$
$\displaystyle\leq\frac{18(n+1)}{7}-c_{1}-c_{2}$
$\displaystyle=\frac{18n}{7}-c_{1}-c_{2}+\frac{18}{7}.$

If (3) applies, then $n_{1}+n_{2}=n$ and so
$e(G)\leq\frac{18n}{7}-c_{1}-c_{2}$. ∎

Let $\mathcal{H}_{0}$ be the class of planar graphs with at least 3 and at
most 6 vertices, and for each positive integer $i$, let $\mathcal{H}_{i}$ be
the union of $\mathcal{H}_{i-1}$ and the class of $C_{7}$-free planar graphs
obtained from applying any of operations (1) - (3) to graphs in
$\mathcal{H}_{i-1}$. Let $\mathcal{H}=\bigcup_{i\geq 0}\mathcal{H}_{i}$. Since
Claims 9.0.1 \- 9.0.2 show that operations (1) - (3) only decrease density, it
follows from Theorem 1.2 that every $n$-vertex planar graph $G$ with $n\geq 7$
in $\mathcal{G}\setminus\mathcal{H}$ satisfies
$e(G)\leq\frac{18n}{7}-\frac{48}{7}$. We now inductively bound the number of
edges of graphs in $\mathcal{H}$.

######  9.0.3.

Let $k$ be non-negative integer, and let $G$ be a $C_{7}$-free $n$-vertex
planar graph in $\mathcal{H}$ with $n\geq 3+2k$. Then either

  1. $(a)$

$e(G)\leq\frac{18n}{7}-\frac{30}{7}-\frac{k}{7}$, or

  2. $(b)$

$G$ is connected and has at most two blocks (maximal connected subgraph
without a cut vertex), each of which is a triangulation on five or six
vertices.

###### Proof.

Note that $n\geq 3$. We apply induction on $n$. First, suppose $n\leq 6$. Then
$k=0$ or $k=1$, and $G\in\mathcal{H}_{0}$. If $e(G)\leq 3n-7$ then $n\leq 6$
implies $e(G)\leq 3n-7\leq\frac{18n}{7}-\frac{31}{7}$ and $(a)$ holds. So
$e(G)=3n-6$ and, hence, $G$ is a triangulation. If $n\leq 4$ then $k=0$ and
$e(G)\leq\frac{18n}{7}-\frac{30}{7}$. If $n\in\\{5,6\\}$ then $(b)$ holds
(with one block).

So we may assume that $n\geq 7$. Then $G\notin\mathcal{H}_{0}$, and thus,
either $G$ is obtained from a graph $G_{1}\in\mathcal{H}$ by applying a single
operation (1), or $G$ is obtained by applying a single operation (2) or (3) to
graphs $G_{1}$ and $G_{2}$ in $\mathcal{H}$.

First suppose that $G$ is obtained from an $n_{1}$-vertex graph
$G_{1}\in\mathcal{H}$ by applying a single operation (1), and that $G$ cannot
be obtained from applying operation (2) or (3) to graphs in $\mathcal{H}$.
Since $n\geq 7$ it follows that $n_{1}\geq 3$, so by induction hypothesis,
either $(a)$ or $(b)$ holds for $G_{1}$. Suppose $(a)$ holds for $G_{1}$.
Thus, since $n_{1}\geq 3+2(k-|S|/2)$,
$e(G_{1})\leq\frac{18n_{1}}{7}-\frac{30}{7}-\frac{(k-|S|/2)}{7}$. Hence, by
Claim 9.0.1, $(a)$ holds for $G$, as operation (1) gives a saving of at least
$1/7$ if $|S|\in[2]$ or $2/7$ if $|S|\in\\{3,4\\}$. So assume $(b)$ holds for
$G_{1}$. It is a straightforward calculation to check that
$e(G_{1})\leq\frac{18n_{1}}{7}-\frac{24}{7}$ (with equality when $G_{1}$ is a
6-vertex triangulation). We may assume that the (18/7)-sparse set $S$ induces
a connected graph, or else we may replace $S$ with one of its subsets. We
consider two cases. If $|S|>1$, then $S$ has at most one neighbor in $G_{1}$,
since $G$ is $C_{7}$-free and $|S|\leq 4$. Since $|S|>1$ and $G$ cannot be
obtained from applying operation (2) or (3) to graphs in $\mathcal{H}$, it
follows that $|S|=2$ and $S$ has no neighbor in $G_{1}$. Let $G_{2}$ be the
graph induced by $S$, which is just a single edge. Then
$e(G_{2})=\frac{18n(G_{2})}{7}-\frac{29}{7}$, and $G$ is obtained by applying
operation (3) to $G_{1}$ and $G_{2}$. So $n\leq 13$ and $k\leq 5$, and since
Claim 9.0.2 gives a savings of $29/7$ it follows that $(a)$ holds for $G$.

So we may assume that $|S|=1$, which implies that $S$ has at most two
neighbors in $G_{1}$. Suppose $S$ has one neighbor in $G_{1}$. Then $n\leq 12$
so $k\leq 4$, and Claim 9.0.2 with $G_{2}$ as a single edge gives a savings of
$11/7$, so $e(G)\leq\frac{18n}{7}-\frac{35}{7}$ and $(a)$ holds for $G$. So we
may assume that $S$ has two neighbors in $G_{1}$ Then since $G$ is
$C_{7}$-free, both neighbors of $S$ are in a block of $G_{1}$ that is a
$5$-vertex triangulation. Since $n\geq 7$, this implies that $G_{1}$ has two
blocks, one of which is a $5$-vertex triangulation. Then either $n=10$ and
$e(G)=20$ (if both blocks of $G_{1}$ have 5 vertices) or $n=11$ and $e(G)=23$
(if one block of $G_{1}$ has 6 vertices). In the former case, $k\leq 3$ and
$e(G)\leq\frac{18n}{7}-\frac{40}{7}$, and in the latter case $k\leq 4$ and
$e(G)\leq\frac{18n}{7}-\frac{37}{7}$, so in either case $(a)$ holds for $G$.

Next suppose that $G$ is obtained by applying a single operation (2) or (3) to
graphs $G_{1}$ and $G_{2}$ in $\mathcal{H}$. For each $i\in[2]$, let
$n_{i}=|G_{i}|$ and let $k_{i}$ be a non-negative integer such that $n_{i}\geq
3+2k_{i}$. Note that we may choose $k_{1},k_{2}$ such that
$k_{1}+k_{2}\in\\{k-1,k\\}$. Also note that $n\geq n_{1}+n_{2}-1\geq
3+2(k_{1}+k_{2}+1)$.

First suppose that outcome $(a)$ holds for both $G_{1}$ and $G_{2}$; so for
$i=1,2$, $e(G_{i})\leq\frac{18n_{i}}{7}-\frac{30}{7}-\frac{k_{i}}{7}$. Then
Claim 9.0.2 with $c_{i}=\frac{30+k_{i}}{7}$ for $i=1,2$ shows that $(a)$ holds
for $G$ as $k\in\\{k_{1}+k_{2},k_{1}+k_{2}+1\\}$.

Now suppose $(a)$ holds for $G_{1}$ and $(b)$ holds for $G_{2}$. Then Claim
9.0.2 shows that $(a)$ holds for $G$ with $k=k_{1}+2$ if $G_{2}$ has one block
and $k=k_{1}+4$ if $G_{2}$ has two blocks.

So we may assume that $(b)$ holds for both $G_{1}$ and $G_{2}$. Suppose $(b)$
does not hold for $G$. Then $G$ consists of 3 or 4 blocks, each of which is a
triangulation with five or six vertices. If $G$ has 4 blocks, then $n\leq 24$
and so $k\leq 10$. A triangulation $B$ with 5 or 6 vertices satisfies
$e(B)\leq\frac{18n(B)}{7}-\frac{24}{7}$, and then applying Claim 9.0.2 three
times gives a savings of at least $18/7$. So
$e(G)\leq\frac{18n}{7}-\frac{42}{7}$, and since $k\leq 10$ it follows that
$(a)$ holds for $G$. If $G$ is connected and has 3 blocks, then $n\leq 16$ and
so $k\leq 6$. Applying Claim 9.0.2 twice gives a savings of at least $12/7$,
so $e(G)\leq\frac{18n}{7}-\frac{36}{7}$, and $(a)$ holds for $G$ since $k\leq
6$. So $G$ is disconnected and has 3 blocks, so $n\leq 18$ and $k\leq 7$.
Since Claim 9.0.2 gives a savings of at least $24/7$ when operation (3) is
applied, $e(G)\leq\frac{18n}{7}-\frac{48}{7}$, and $(a)$ holds for $G$ since
$k\leq 7$. ∎

Let $G$ be an $n$-vertex $C_{7}$-free planar graph with $n>38$. If
$G\in\mathcal{G}\setminus\mathcal{H}$ then
$e(G)\leq\frac{18n}{7}-\frac{48}{7}$. If $G\in\mathcal{H}$, then Claim 9.0.3
applies with $k=18$ and outcome $(a)$ holds, so
$e(G)\leq\frac{18n}{7}-\frac{48}{7}$, as desired. ∎

##  10 Future Work

As discussed in Section 1, the conjecture of Ghosh et al. that
$\operatorname{ex}_{\mathcal{P}}(n,C_{\ell})\leq\frac{3(\ell-1)}{\ell}n-\frac{6(\ell+1)}{\ell}$
for all $\ell\geq 7$ and all sufficiently large $n$ is false for all $\ell\geq
11$, but true for $\ell=7$ by Theorem 1.1. Is this conjecture true for
$\ell\in\\{8,9,10\\}$? We believe that the answer is yes for $\ell=8$, and
that this can be proven using existing techniques and extensive case work.
However, we believe that for $\ell=9$,
$\operatorname{ex}_{\mathcal{P}}(n,C_{\ell})>\frac{3(\ell-1)}{\ell}n-\frac{6(\ell+1)}{\ell}$
for infinitely many $n$, and we plan to prove this via a construction in a
forthcoming paper. For $\ell=10$ the correct answer is unclear.

We mention one other direction that could be approached using techniques from
this paper. For each $\ell\geq 4$, let $\Theta_{\ell}$ denote the family of
graphs (call _theta graphs_) obtained by adding an edge between two non-
adjacent vertices of $C_{\ell}$, and write
$\operatorname{ex}_{\mathcal{P}}(n,\Theta_{\ell})$ for the maximum number of
edges in an $n$-vertex planar graph that contains no graph in $\Theta_{\ell}$
as a subgraph. Sharp upper bounds for
$\operatorname{ex}_{\mathcal{P}}(n,\Theta_{\ell})$ are known for
$\ell\in\\{4,5,6\\}$ by results of Lan, Shi and Song [8] and Ghosh, Győri,
Paulos, Xiao, and Zamora [6], but no sharp upper bound is known for $\ell\geq
7$. Due to the importance of triangular-blocks with a chord in our main proof,
we believe that our techniques could make progress towards a sharp upper bound
on $\operatorname{ex}_{\mathcal{P}}(n,\Theta_{7})$.

## References

  * [1] N. Alon and C. Shikhelman.  Many T copies in H-free graphs.  Journal of Combinatorial Theory, Series B, 121:146–172, 2016.
  * [2] D.W. Cranston, B. Lidický, X. Liu, and A. Shantanam.  Planar Turán numbers of cycles: a counterexample.  Electron. J. Combin., 29, 2022.
  * [3] C. Dowden.  Extremal $C_{4}$‐free/$C_{5}$‐free planar graphs.  Journal of Graph Theory, 83, 2015.
  * [4] P. Erdős and A. Stone.  On the structure of linear graphs.  Bull. Amer. Math. Soc., 52:1087–1091, 1946.
  * [5] D. Ghosh, E. Győri, R. R. Martin, A. Paulos, and C. Xiao.  Planar Turán number of the 6-cycle.  SIAM J. Disc. Math., 36(3):2028–2050, 2022.
  * [6] D. Ghosh, E. Győri, A. Paulos, C. Xiao, and O. Zamora.  Planar Turán number of the $\Theta_{6}$.  Online Preprint: arXiv:2006.00994v1, 2020.
  * [7] P. Keevash.  Hypergraph Turán problems.  Surveys in Combinatorics, pages 83–140, 2011.
  * [8] Y. Lan, Y. Shi, and Z.-X. Song.  Extremal theta-free planar graphs.  Discrete Mathematics, 342(12):111610, 2019.
  * [9] Y. Lan, Y. Shi, and Z.-X. Song.  Planar Turán number and planar anti-ramsey number of graphs.  Oper. Res. Trans., 25(3):201–216, 2021.
  * [10] Y. Lan and Z.-X. Song.  An improved lower bound for the planar Turán number of cycles.  Online Preprint: arXiv:2209.01312, 2022.
  * [11] David Offner.  Some Turán type results on the hypercube.  Discrete Mathematics, 309(9):2905–2912, 2009.
  * [12] V. Rödl and M. Schacht.  Extremal results in random graphs.  Bolyai Soc. Math. Stud., 25:535–583, 2013.
  * [13] P. Turán.  On an extremal problem in graph theory.  Mat. Fiz. Lapok, 48:436–452, 1941.