=20 pt

Given a graph $F$, the planar Turán number of $F$, denoted $\ex_{\p}(n, F)$, is the maximum number of edges in an $n$-vertex $F$-free planar graph. Such an extremal graph problem was initiated by Dowden while determining sharp upper bound for $\ex_{\p}(n,C_4)$ and $\ex_{\p}(n,C_5)$, where $C_4$ and $C_5$ are cycles of length four and five respectively.  In this paper we determined an upper bound for $\ex_{\p}(n,S_{2,2})$, $\ex_{\p}(n,S_{2,3})$, $\ex_{\p}(n,S_{2,4})$, $\ex_{\p}(n,S_{2,5})$, $\ex_{\p}(n,S_{3,3})$ and $\ex_{\p}(n,S_{3,4})$, where $S_{m,n}$ is a double star with $m$ and $n$ leafs. Moreover, the bound for $\ex_{\p}(n,S_{2,2})$ is sharp.

§ INTRODUCTION

One of the famous problems in extremal graph theory is determining the number of edges in an $n$-vertex graph to force a particular graph structure.
The well-known result of Turán's <cit.> gives the maximum number of edges in an $n$-vertex graph containing no complete graph of a given order.  Recall that the Turán number of a graph $H$, denoted by $\text{ex}(n, H)$, is the maximum number of edges in an $n$-vertex graph that does not contain $H$ as a subgraph, and $\text{EX}(n,H)$ denotes the set of extremal graphs, i.e. the set of all $n$-vertex, $H$-free graph $G$ such that $e(G)=\text{ex}(n,H)$.  Erdős, Stone and Simonovits <cit.> gave a more generalized result where they determined the asymptotics of $\text{ex}(n,F)$ for all non-bipartite graphs $F$.  They proved that $\text{ex}(n,F)=(1-\frac{1}{\chi(F)-1})\binom{n}{2}+o(n^{2})$, where $\chi(F)$ denotes the chromatic number of $F$.

Over the last decade, a considerable amount of research work has been carried out on Turán type problems, for example, when the host graphs are $K_n$, $k$-uniform hypergraphs, or $k$-partite graphs, see <cit.>.  In 2015, Dowden <cit.> initiated the study of Turán-type problems when the host graph is a family of planar graphs
i.e., how many edges a planar graph on $n$ vertices can have without containing a given smaller graph? The planar Turán number of a graph $F$,  denoted by $\text{ex}_{\mathcal{P}}(n, F)$, is the maximum number of edges in a planar graph on $n$ vertices containing no $F$ as a subgraph.  Dowden <cit.> determined sharp upper bound for $\ex_{\p}(n, C_4)$ and $\ex_{\p}(n,C_5)$, where $C_4$ and $C_5$ are cycle of length four and five respectively. Very recently, Ghosh et.al. <cit.> obtained sharp upper bound for $\ex_{\p}(n, C_6)$, where $C_6$ is cycle of length $6$.

The analog to Turán theorem in the case of planar graphs is fairly trivial. Since $K_5$ is not planar, there are only two meaningful cases. For the $K_{3}$, the extremal number of edges is $2n-4$, and the extremal graph is $K_{2,n-2}$ (since all faces have size four when drawn in the plane).  Note that there exist planar triangulations not containing $K_4$ (e.g., take a cycle of length $n - 2$ and then add two new vertices that are both adjacent to all those in the cycle), and so the extremal number in the case of $K_4$ is $3n - 6$. The planar Turán number when the forbidden subgraph is a star is also fairly trivial.  The authors in <cit.> proved that $\ex_{\mathcal{P}} (n, H) = 3n - 6$ for all $H$ with $n > |H|+2$ and either $\chi(H) = 4$ or $\chi(H) = 3$ and $\Delta(H) > 7$. They also completely determine $\ex_P (n, H)$ when $H$ is a wheel or a star, and the case when H is a $(t, r)$-fan, that is, $H$ is isomorphic to $K_1 + tK_{r-1}$, where $t > 2$  and $r > 3$ are integers. The next most natural type of graph to investigate is perhaps a path, in analog with Erdos-Gallai theorem <cit.>, which determined the extremal Turán number for paths. We refer the reader to <cit.> and <cit.>, for extremal planar Turán number for paths of length $\{6, 7, 8, 9, 10, 11\}$. Planar Turán number of other graphs, for instance, wheels and Theta graphs also considered. We refer the reader to <cit.> for detailed results. The next natural extension of the topic is considering double stars as the forbidden graph.

An ($m$,$n$)-double star, denoted by $S_{m,n}$, is the graph  obtained by taking an edge, say $xy$, and joining one of its end vertex, say $x$, with $m$ vertices and  the other end vertex, $y$, with $n$ vertices which are different from the $m$ vertices.  The edge $xy$ is called backbone of the double star. The set of all vertices which are adjacent to an end vertex of the backbone is called a leaf-set of the double star. See Figure <ref>, showing an $m$-$n$ double star such that the backbone is $xy$ and the leaf-sets are $\{x_1,x_2,\dots,x_m\}$ and $\{y_1,y_2,\dots,y_n\}$ respectively.

Let $xy$ be an edge in $G$ and $x'$ be a vertex in $N(x)\backslash \{y\}$. An edge in $G$ which is incident to $x'$ is called an outer edge of $x'$ if its end vertex other than $x'$ is not in $N(x)\cup N(y)$. Otherwise, we call the edge as inner edge of $x'$.

[black, ultra thick](-10,0)–(10,0)(10,0)–(20,10)(10,0)–(20,6)(10,0)–(20,2)(10,0)–(20,-8)(-10,0)–(-20,10)(-10,0)–(-20,6)(-10,0)–(-20,2)(-10,0)–(-20,-8);
at (-10,-2) $x$;
at (10,-2) $y$;
at (22,10) $y_1$;
at (22,6) $y_2$;
at (22,2) $y_3$;
at (22,-8) $y_n$;
at (-22,10) $x_1$;
at (-22,6) $x_2$;
at (-22,2) $x_3$;
at (-22,-8) $x_m$;

A double star $S_{m,n}$ with $m$ and $n$ leafs.

In this paper, we address the upper bounds of planar Turán number of  the following double stars: $S_{2,2}$, $S_{2,3}$, $S_{2,4}$, $S_{2,5}$, $S_{3,3}$ and $S_{3,4}$.  Moreover, the bound for $\ex_{\p}(n,S_{2,2})$ is sharp and the bound for $\ex_{\p}(n,S_{3,3})$ is sharp up-to a linear term.  Before proceeding to our results, we mention notations and terminologies to be used in next.

All the graphs we consider in this paper are finite and simple. We denote the vertex and edge sets of a graph $G$ by $V(G)$ and $E(G)$ respectively. The size of $V(G)$ and $E(G)$ are denoted by $v(G)$ and $e(G)$ respectively. The subgraph induced by $S\subseteq V(G)$, is denoted by $G[S]$. For a vertex $v\in V(G)$, degree of $v$ is denoted by $d(v)$. Moreover, $N(v)$ denotes the set of vertices in $G$ which are adjacent to $v$. The minimum and maximum degree of $G$ is denoted by $\delta(G)$ and $\Delta(G)$ respectively. Let $A$ and $B$ be disjoint subsets of $V(G)$. The number of edges in $G$ that joins a vertex in $A$ and a vertex in $B$ is denoted by $e(A,B)$.  An $m$-$n$ edge is an edge such that end vertices of the edge are with degree $m$ and $n$.

Given a graph $G$ and $H$ a subgraph of $G$.   Let $v$ be a vertex in $H$.  $\text{Outer edges}_{H}$ from $v$ is the maximum number of edges from $v$ to $G-H$.  Where as, $\text{inner edges}_{H}$ from $v$ is the maximum number of edges from $v$ to $H$.

The following Theorem summarizes the main results:

The planar Turán number of double stars $S_{m,n}$ for given values of $\{m,n\}$ are as follows:

* For any $n\geq 16$, $\ex_{\p}(n,S_{2,2})=2n-4$.

* For any $n\geq 1$, $2n-4\leq \ex_{\mathcal{P}}(n,S_{2,3})\leq 2n.$

* For any $n\geq 12$, $\ex_{\mathcal{P}}(n,S_{2,4})\leq\frac{17}{7}n-2.$

* For $n\geq1$, $\ex_{\mathcal{P}}(n,S_{2,5})\leq\frac{20}{7}n.$

* For $n\geq 3$, $\frac{5}{2}n-5\leq\ex_{\mathcal{P}}(n,S_{3,3})\leq\frac{5}{2}n-2.$

* For $n\geq 1$, $\ex_{\mathcal{P}}(n,S_{3,4})\leq\frac{20}{7}n.$

§ PLANAR TURÁN NUMBER OF S2,2

Let $G$ be an $n$-vertex,  ($n\neq 5$) $S_{2,2}$-free graph. Then $e(G)\leq 2n-2$.

It can be checked that the lemma holds for $n\leq 4$.  Suppose that $G$ contains $6$ vertices. Notice that there are only two $6$-vertex maximal planar graphs $M_1$ and $M_2$ as shown in Figure <ref>. It can be checked that any $M_1^-$ and $M_2^-$ contains an $S_{2,2}$. Thus $e(G)\leq 10=2n-2$.

at (0,-11) $M_1$;
at (0,-11) $M_2$;

The two $6$-vertex maximal planar graphs.

Now let $G$ be a $7$-vertex $S_{2,2}$-free planar graph. We assume that $G$ contains no vertex of degree at most $2$. Otherwise, we are done by induction. Moreover, there is no vertex of degree at least $5$ in $G$. Indeed, suppose there is $x\in V(G)$ such that $d(x)=k$, where $k\geq 5$. In this case, each vertex in $N(x)$ must be of degree at most $2$ and we can proceed by induction. Otherwise, it is easy to find an $S_{2,2}$ in $G$, which is a contradiction.

Assume that $\Delta(G)\leq4$. Let the number of vertices in $G$ with degree at most $3$ be $k$. Hence $G$ contains $n-k$ vertices of degree $4$, which implies
and if there are at least $4$ vertices of degree at most $3$, then we are done.

Let $v$ be a degree $4$ vertex in $G$. If each vertex in $N(v)$ is of degree at most $3$, then we done. So there is a vertex of degree $4$ in $N(v)$. Let $u\in N(v)$ be such a vertex.  Which means $uv$ is a $4$-$4$ edge in $G$. Since $G$ is $S_{2,2}$-free, $uv$ must be contained in $3$ triangles. Let $N(u)\cap N(v)=\{x_1,x_2,x_3\}$ and $S=V(G)\backslash\{u,v,x_1,x_2,x_3\}$. Observe that no vertex in $\{x_1,x_2,x_3\}$ is adjacent to a vertex in $S$ and there are at least two vertices in the subgraph induced by $\{u,v,x_1,x_2,x_3\}$. Since $n\geq 7$, it is easy to find two vertices in $S$ with degree at most $3$. Hence we are done.

Let $G$ be an $n$-vertex ($n\geq 8$) $S_{2,2}$-free graph. If there is a vertex with degree at least $5$, then $e(G)\leq 2n-4$.

Let $x \in V (G)$ such that $d(x) = k\geq 5$. Let $N(x) = \{x_1, x_2, x_3,\dots , x_k\}$, and $S$ be the set of vertices in $V(G)\backslash N(x)$. Notice that each vertex in $N(x)$ is adjacent to at most one vertex in $N(x)$. Otherwise, it is easy to show $G$ contains an $S_{2,2}$. Similarly, for an edge $x_ix_j\in N(x)$, there is no vertex in $S$ which is adjacent to either $x_i$ or $x_j$. Thus the number of edges joining a vertex in $N(x)$ and a vertex in $S$ is at most $k$. Observe that $|S|= n-k-1$.

If $|S|\neq 5$, using Lemma <ref>, $e(G[S]) \leq 2(n-k-1)-2.$ Therefore $e(G) \leq 2(n-k-1)-2+2k =2n-4$, and we are done.

Let $|S|= 5$. Let the graph induced by $S$ be a $K_5^-$.  Since $G$ is $S_{2,2}$-free, no vertex in $N(x)$ is adjacent to one or two vertices in $S$.  This implies, $e(G[s]) = 9$, $e(G[N(x)])\leq \frac{k}{2}$. Hence $e(G)\leq k + \frac{k}{2} + 9$. Since $n = k + 6$, we have $e(G) \leq (n-6) + \frac{n-6}{2}+ 9 = \frac{3n}{2}\leq 2n-4$ for $n\geq 8$.

The lower bound is attained by considering the graph $K_{2,n-2}$, which is $S_{2,2}$-free and contains $2n-4$ edges. From Lemma <ref>, we may assume that $\Delta(G)\leq 4$. Let $k$ be the number of vertices in $G$ whose degree is at most $3$. Then $e(G)\leq \frac{4(n-k)+3k}{2}=2n-\frac{k}{2}$.

If $k\geq 8$, then we are done. So we may assume that the number of degree $4$ vertices in $G$ is at least $9$. We need the following two claims to complete proof the theorem.

There is no degree $4$ vertex in $G$ such that all of its neighbors are of degree at most $3$.

Suppose not.  Let $x$ be a degree $4$ vertex in $G$ such that $d(y)\leq 3$ for all $y\in N(x)$. Let $N(x)=\{x_1,x_2,x_3,x_4\}$ and $S=V(G)\backslash \{x,x_1,x_2,x_3,x_4\}$. Since a vertex in $N(x)$ can not be adjacent to a vertex in $N(x)$ and a vertex in $S$ at the same time, the number of edges in $G[N(x)]$ and edges joining a vertex in $N(x)$ and a vertex in $S$ is at most $4$. Therefore, using Lemma <ref>, $e(G)=e(G[S])+8\leq 2(n-5)-2+8=2n-4.$

The number of $4$-$4$ edge matchings in $G$ is least $3$.

Suppose not. Let the number of $4$-$4$ edge matchings in $G$ be $2$.  Denote the $4$-$4$ edge matchings by $uv$ and $xy$. Each of the edges is contained in $3$ triangles. Let $N(u)\cap N(v)=\{u_1,u_2,u_3\}$ and $N(x)\cap N(y)=\{x_1,x_2,x_3\}$. Since $G$ is an $S_{2,2}$-free graph, no vertex in $\{u_1,u_2,u_3\}$ is adjacent with a vertex in $V(G)\backslash \{x,y,x_1,x_2,x_3\}$ and no vertex in $\{x_1,x_2,x_3\}$ is adjacent with a vertex in $V(G)\backslash \{u,v,u_1,u_2,u_3\}$. Moreover, at least two vertices in $\{x_1,x_2,x_3\}$ and in $\{u_1,u_2,u_3\}$ are of degree at most three. Since the number of degree $4$ vertices in $G$ is at least $9$, then there is a degree $4$ vertex, say $z$,  in $V(G)\backslash \{x,y,u,v,x_1,x_2,x_3,u_1,u_2,u_3\}$ such that $d(t)\leq 3$ for every $t\in N(z)$, which is a contradiction to Claim <ref>. Similar argument can be given if we assume that the number of $4$-$4$ edge matching in $G$ is of size $1$.

Now suppose the number of $4$-$4$ edge matchings in $G$ is least $3$. We distinguish the following two cases.

The number of $4$-$4$ edge matchings in $G$ is least $4$.

Denote the $4$-$4$ edge matchings in $G$ by $x_1x_2$, $x_3x_4$, $x_5x_6$ and $x_7x_8$ respectively. Recall that each edge is contained in $3$ triangles. Moreover, at least two vertices in $N(x_i)\cap N(x_{i+1})$ is of degree at most $3$. So we have at least $8$ vertices in $G$ whose degree is at most $3$, $i\in\{1,3,5,7\}$. Hence we are done in this case.

The number of $4$-$4$ edge matchings in $G$ is exactly $3$.

Denote the $4$-$4$ edge matchings in $G$ by $x_1x_2, x_3x_4$ and $x_5x_6$ respectively. Notice that at least two vertices in $N(x_i)\cap N(x_{i+1})$ is of degree at most $3$, $i\in\{1,3,5\}$, which implies $G$ contains at least $6$ vertices whose degree is at most $3$. Moreover if a vertex in $N(x_i)\cap N(x_{i+1})$, for some $i\in\{1,3,5\}$, is of degree at most $2$, then the remaining two vertices are of degree at most $3$.  Observe that in this case, $e(G)\leq\frac{4(n-7)+3\times6+2}{2}=2n-4$ and we are done.

So we assume exactly two vertices in $N(x_i)\cap N(x_{i+1})$ are of degree $3$, $i\in\{1,3,5\}$. In this case, the remaining vertex in $N(x_i)\cap N(x_{i+1})$ is of degree $4$. That means a $K_5^-$ is the vertices induced by $\{x_i,x_{i+1}\}\cup N(x_i)\cap N(x_{i+1})$, $i\in\{1,3,5\}$, and it is a component in $G$.

If $n=16$, then there is an isolated vertex. In this case, $e(G)=27<2n-4.$ Considering that the number of $4$-$4$ edge matching in $G$ is $3$, it is easy to find $2$ more vertices of degree at most $3$, other than the $6$ vertices in $N(x_i)\cap N(x_{i+1})$, $i\in\{1,3,5\}$, whose degree is at most $3$. So this completes the proof of Theorem <ref>(i).

§ PLANAR TURÁN NUMBER OF S2,3

Let $G$ be an $n$-vertex $S_{2,3}$-free plane graph. The lower bound is true as $G$ is an $S_{2,2}$-free graph and by Theorem <ref>(i).

Clearly, if the maximum degree in $G$ is at most $4$, $e(G)\leq 2n$. Now we separate the rest of the proof into $2$ cases:

Case 1. There exists a vertex $v\in V(G)$, such that $d(v)\geq 6$.

It is easy to check that for each $u\in N(v)$, $d(u)\leq 2$, otherwise, we find a copy of $S_{2,3}$ in $G$. Delete a vertex $u\in N(v)$, then the number of deleted edges is at most $2$. By the induction hypothesis, we get $e(G-u)\leq 2(n-1)$. Hence, $e(G)=e(G-u)+d(u)\leq 2+2(n-1)=2n$.

Case 2. There exists a vertex $v\in V(G)$, such that $d(v)=5$.

It is easy to check that for each $u\in N(v)$, if $u$ has an outgoing edge, that is $N(u)\cap \{v\cup N(v)\}\neq \emptyset$, then $d(u)=2$. Otherwise, $G$ contains an $S_{2,3}$.

(i) There exists a vertex $u\in N(v)$, such that $d(u)\leq2$. Similarly as in Case $1$, we are done by induction.

(ii) There exists a vertex $u\in N(v)$, such that $d(u)\geq 3$. It is clear that for each $u\in N(v)$, $u$ has no outgoing edge, that is $N(u)\cap \{v\cup N(v)\}= \emptyset$. Then $e(G[v\cup N(v)])\leq 3\times 6-6=12$. By the induction hypothesis, $e(G-\{v\cup N(v)\})\leq 2(n-6)$. Therefore, $e(G)=e(G-\{v\cup N(v)\})+e(G[v\cup N(v)])\leq 2n$.

§ PLANAR TURÁN NUMBER OF S2,4

For the rest of the section let $G$ be an $n$-vertex $S_{2,4}$-free planar graph.  Notice that, since $S_{2,4}$ contains $8$ vertices, a maximal planar graph with $n\leq 7$ vertices, does not contain an $S_{2,4}$. Recall that, an $n$-vertex maximal planar graph contains $3n-6$. Since, $3n-6\leq \frac{17}{7}n-2$ for $n\leq 7$, Theorem <ref>(iii), also holds for all $n$, $1\leq n\leq 7$.

If $G$ contains a bridge or a $2$-cut, then $e(G)\leq \frac{17}{7}n-2.$

Suppose $G$ contains a $2$-cut.  Let $G=G_1\cup G_2$ be the two subgraphs with $n_1$ and $n_2$ vertices respectively and are joined by a $2$-cut.  Applying induction hypothesis to each one of them, we get

\begin{equation*}
\end{equation*}

Hence we are done. We can prove similarly for the case of $G$ having a bridge.

The following claims deal with the different degree pairs:

If $G$ contains a vertex of degree greater than or equal to $7$, $e(G)\leq \frac{17}{7}n-2.$

Let $v\in V(G)$, such that $d(v)\geq 7$.  It is easy to check that for each $u\in N(v)$, $d(u)\leq 2$, otherwise, we find a copy of $S_{2,4}$ in $G$. Delete a vertex $u\in N(v)$, then the number of deleted edges is at most $2$. By the induction hypothesis, we get $e(G-u)\leq \frac{17}{7}(n-1)-2$. Hence, $e(G)=e(G-u)+d(u)\leq \frac{17}{7}(n-1)-2+2=\frac{17}{7}(n-1)$.

Given a graph $G$.  Let $H$ be a subgraph of $G$ and $v$ be a vertex in $H$.  Recall, the maximum number of edges from $v$ to $G-H$ and the maximum number of edges from $v$ to $H$ is denoted by outer and inner edges from $v$ respectively.  Let $n$ be a positive integer and $S_1$ be another subgraph of $G$.  The number of outer edges from the vertices of $S_1$ to $G-H$ is denoted by $n_{\text{out of $S_1$}}$.  Whereas $n_{\text{in $S_1$}}$ denotes the total number of inner edges from vertices in $S_1$ to other vertices in $S_1$.

If $G$ contain a degree $6$ vertex, $e(G)\leq \frac{17}{7}n-2.$

Let $v\in V(G)$, such that $d(v)=6$ and let $H:=N(v)\cup \{v\}$.  Suppose we delete the $7$ vertices in $H$.  It is easy to check that each $u\in N(v)$ can only have one outer edge.  Note that, if $u\in N(v)$ has an outer edge, it is not adjacent to any other $x\in N(v)$.  Hence $u$ is a degree $2$ vertex, and we are done by induction.  In the other case, the neighbors of $v$ have no outer edges.  Consider the maximum planar graph on the vertices of $H$.  The maximum number of edges deleted is $3\times 7-6=15$,  and again we are done by induction.

(x) at (-12,0);
(y) at (12,0);
(a) at (0,27);
(b) at (0,18);
(c) at (0,9);
(d) at (0,-9);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[fill=black] (x) circle(∘)  node[label=below:$x$] ;
[fill=black] (y) circle(∘)  node[label=below:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;

$G$ has a $5-5$ edge $xy$, with $4$ triangles sitting on the edge $xy$.

(x) at (-12,0);
(y) at (12,0);
(a) at (0,18);
(b) at (0,9);
(c) at (0,-9);
(d) at (-21,0);
(e) at (21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (x) – (d);
[thick] (e) – (y);
[fill=black] (x) circle(∘)  node[label=below:$x$] ;
[fill=black] (y) circle(∘)  node[label=below:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=below:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
at (0,-21)(i);

(x) at (-12,0);
(y) at (12,0);
(a) at (0,18);
(b) at (0,9);
(c) at (0,-9);
(d) at (-21,0);
(e) at (21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (x) – (d);
[thick] (e) – (y);
[thick] (d) – (a);
[fill=black] (x) circle(∘)  node[label=below:$x$] ;
[fill=black] (y) circle(∘)  node[label=below:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=below:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
at (0,-21)(ii);

(x) at (-12,0);
(y) at (12,0);
(a) at (0,18);
(b) at (0,9);
(c) at (0,-9);
(d) at (-21,0);
(e) at (21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (x) – (d);
[thick] (e) – (y);
[thick] (d) – (a);
[thick] (e) – (a);
[fill=black] (x) circle(∘)  node[label=below:$x$] ;
[fill=black] (y) circle(∘)  node[label=below:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=below:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
at (0,-21)(iii);

(x) at (-12,0);
(y) at (12,0);
(a) at (0,18);
(b) at (0,9);
(c) at (0,-9);
(d) at (-21,0);
(e) at (21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (x) – (d);
[thick] (e) – (y);
[thick] (d) – (a);
[thick] (e) – (c);
[fill=black] (x) circle(∘)  node[label=below:$x$] ;
[fill=black] (y) circle(∘)  node[label=above:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=below:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
at (0,-21)(iv);

(x) at (-12,0);
(y) at (12,0);
(a) at (0,18);
(b) at (0,9);
(c) at (0,-9);
(d) at (-21,0);
(e) at (21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (x) – (d);
[thick] (e) – (y);
[thick] (d) – (a);
[thick] (d) – (c);
[fill=black] (x) circle(∘)  node[label=above:$x$] ;
[fill=black] (y) circle(∘)  node[label=above:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=below:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
at (0,-21)(v);

(x) at (-12,0);
(y) at (12,0);
(a) at (0,18);
(b) at (0,9);
(c) at (0,-9);
(d) at (-21,0);
(e) at (21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (x) – (d);
[thick] (e) – (y);
[thick] (d) – (a);
[thick] (d) – (c);
[thick] (e) – (c);

[fill=black] (x) circle(∘)  node[label=above:$x$] ;
[fill=black] (y) circle(∘)  node[label=above:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=below:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
at (0,-21)(vi);

(x) at (-12,0);
(y) at (12,0);
(a) at (0,18);
(b) at (0,9);
(c) at (0,-9);
(d) at (-21,0);
(e) at (21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (x) – (d);
[thick] (e) – (y);
[thick] (d) – (a);
[thick] (d) – (c);
[thick] (e)..controls (27,0) and (27,9) ..(b);

[fill=black] (x) circle(∘)  node[label=above:$x$] ;
[fill=black] (y) circle(∘)  node[label=above:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=below:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
at (0,-21)(vii);

(x) at (-12,0);
(y) at (12,0);
(a) at (0,18);
(b) at (0,9);
(c) at (0,-9);
(d) at (-21,0);
(e) at (21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (x) – (d);
[thick] (e) – (y);
[thick] (d) – (a);
[thick] (d) – (c);
[thick] (e) – (c);
[thick] (e) – (a);

[fill=black] (x) circle(∘)  node[label=above:$x$] ;
[fill=black] (y) circle(∘)  node[label=above:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=below:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
at (0,-21)(viii);

(x) at (-12,0);
(y) at (12,0);
(a) at (0,18);
(b) at (0,9);
(c) at (0,-9);
(d) at (-21,0);
(e) at (21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (x) – (d);
[thick] (e) – (y);
[thick] (d) – (a);
[thick] (d) – (c);
[thick] (e) – (a);
[thick] (e)..controls (27,0) and (27,9) ..(b);
[fill=black] (x) circle(∘)  node[label=above:$x$] ;
[fill=black] (y) circle(∘)  node[label=above:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=below:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
at (0,-21)(ix);

[foo bar2]$G$ has a $5-5$ edge $xy$, with $3$ triangles sitting on the edge $xy$.

* The vertices $d$ and $e$ have no neighbors in $S_1$.

* The vertex $d$ has one neighbor in $S_1$, and $e$ has none.

* The vertices $d$ and $e$ have one common neighbor in $S_1$.

* The vertices $d$ and $e$ have one distinct neighbor in $S_1$.

* The vertex $d$ has two neighbors in $S_1$, while $e$ has none.

* The vertex $d$ is the neighbor of $a$ and $c$, and while $e$ is the neighbor of $c$.

* The vertex $d$ is the neighbor of $a$ and $c$, while $e$ is the neighbor of $b$.

* The vertices $d$ and $e$ are neighbors of $a$ and $c$ both.

* The vertex $d$ is the neighbor of $a$ and $c$, while $e$ is the neighbor of $a$ and $b$.

If $G$ contains a $5-5$ edge, then $e(G)\leq \frac{17}{7}n-2.$

Let $xy\in E(G)$ be a $5-5$ edge.  We subdivide the cases based on the number of triangles sitting on the edge $xy$.

* There are $4$ triangles sitting on the edge $xy$. Let $a,b,c$ and $d$ be vertices in $G$ which are adjacent to both $x$ and $y$ (see Figure <ref>).  Denote $S_1=\{a,b,c,d\}$ and $H=\{x,y,a,b,c,d\}$.  Delete the vertices in $H$.  If any vertex or vertices in $S_1$ has an outer edge, we get a bridge or a $2$-cut and are done by Lemma <ref>.  Consider a maximal planar graph on the $6$ vertices of $H$.  The maximum number of edges deleted is thus at most $3\times 6-6=12.$  We are done by induction.

* There are $3$ triangles sitting on the edge $xy$.  Let $a,b$ and $c$ be vertices in $G$ which are adjacent to both $x$ and $y$. Let $d$ be the vertex adjacent to $x$ but not adjacent to $y$, and $e$ be the vertex adjacent to $y$ and but not adjacent to $x$.   Denote $S_1=\{a,b,c\}$ and $H=\{x,y\}\cup S_1\cup\{d,e\}$.  Deleting the vertices in $H$.  The vertices $d$ and $e$ can have at most one outer edge.  We differentiate the cases based on the neighbors of $d$ and $e$ as follows:

* The vertices $d$ and $e$ have no neighbors in $S_1$, see Figure <ref>(i).  The vertices in $S_1$ can have one outer edge each and can form a path of length $2$ in $S_1$.  If the vertices $d$ and $e$ are adjacent, then both of them cannot have an outer edge.  Otherwise, we have an $S_{2,4}$ with $dx$ (or $ey$) as the backbone.  Hence in this case, the maximum number of edges deleted is at most $9+2_{\text{in $S_1$}}+3_{\text{out of $S_1$}}+2_{\text{out of $d,e$}}=16$.

* One of the vertices $e$ or $f$ has one neighbor in $S_1$, and the other has none.
Suppose $a$ is the neighbor of $d$, see Figure <ref>(ii).  Note that $a$ cannot have an outer edge.  Otherwise we have an $S_{2,4}$ with $ay$ as the backbone.  If the vertices $d$ and $e$ are adjacent, then both of them cannot have an outer edge.  Similarly as before, the vertices $b$ and $c$ can have one outer edge each and the vertices $\{a,b,c\}$ can form a path of length $2$ in $S_1$.  Hence in this case, the maximum number of edges deleted is at most $10+2_{\text{in $S_1$}}+2_{\text{out of $S_1$}}+2_{\text{out of $d,e$}}=16$.

* The vertices $d$ and $e$ have one neighbor in $S_1$.
Suppose $a$ is the common neighbor of $d$ and $e$, see Figure <ref>(iii).  Similarly as before, $a$ cannot have an outer edge.  If the vertices $d$ and $e$ are adjacent, then both of them cannot have an outer edge.  The vertices $b$ and $c$ can have one outer edge each and the vertices $\{a,b,c\}$ can form a path of length $2$ in $S_1$.  Hence in this case, the maximum number of edges deleted is at most $11+2_{\text{in $S_1$}}+2_{\text{out of $S_1$}}+2_{\text{out of $d,e$}}=17$.
Suppose $a$ is the neighbor of $d$ and $c$ is the neighbor of $e$, see Figure <ref>(iv).  Similarly as before, $a$ and $c$ both cannot have an outer edge.  The vertex $b$ can have one outer edge and the vertices $\{a,b,c\}$ can form a path of length $2$ in $S_1$.  Thus the maximum number of edges deleted is at most $11+2_{\text{in $S_1$}}+1_{\text{out of $S_1$}}+2_{\text{out of $d,e$}}=16$.

* One of the vertices $d$ or $e$ has two neighbors in $S_1$, while the other has none.
Suppose $d$ is the neighbor of $a$ and $c$, see Figure <ref>(v).  Similarly as before, $a$ and $c$ both cannot have an outer edge.  The vertex $b$ can have one outer edge and the vertices $\{a,b,c\}$ can form a path of length $2$ in $S_1$.  Thus the maximum number of edges deleted is at most $11+2_{\text{in $S_1$}}+1_{\text{out of $S_1$}}+2_{\text{out of $d,e$}}=16$.

* One of the vertices $d$ or $e$ has two neighbors in $S_1$, while the other has one neighbor.
Suppose $d$ is the neighbor of $a$ and $c$, and $e$ is the neighbor of $c$ (see Figure <ref>(vi)).  Similarly as before, $a$ and $c$ both cannot have an outer edge.  The vertex $b$ can have one outer edge and the vertices $\{a,b,c\}$ can form a path of length $2$ in $S_1$.  Thus the maximum number of edges deleted is at most $12+2_{\text{in $S_1$}}+1_{\text{out of $S_1$}}+2_{\text{out of $d,e$}}=17$.
In the other case, assume that $d$ is the neighbor of $a$ and $c$, and $e$ is the neighbor of $b$ (see Figure <ref>(vii)).  The vertices $a,b$ and $c$ cannot have an outer edge, but they can form a path of length $2$ in $S_1$.  Thus the maximum number of edges deleted is at most $12+2_{\text{in $S_1$}}+2_{\text{out of $d,e$}}=16$.

* Both the vertices $d$ and $e$ have two neighbors in $S_1$.  Suppose $d$ and $e$ are neighbors of $a$ and $c$ both (see Figure <ref>(viii)).  Similarly as before, $a$ and $c$ both cannot have an outer edge.  If the vertex $b$ has one outer edge, then that outer edge is a bridge and we are done by Lemma <ref>.  The vertices $\{a,b,c\}$ can form a path of length $2$ in $S_1$.  Thus the maximum number of edges deleted is at most $13+2_{\text{in $S_1$}}+2_{\text{out of $d,e$}}=17$.
On the other hand, assume $d$ is the neighbor of $a$ and $c$, while $e$ is the neighbor of $a$ and $b$ (see Figure <ref>(ix)).  The vertices $a,b$ and $c$ cannot have an outer edge, but they can form a path of length $2$ in $S_1$.  Thus the maximum number of edges deleted is at most $13+2_{\text{in $S_1$}}+2_{\text{out of $d,e$}}=17$.

Using the induction hypothesis,
$$e(G)\leq e(G-H)+15\leq \frac{17}{7}(n-7)-2+17=\frac{17}{7}n-2.$$
This completes the proof.

Take $x,y\in V(G)$.  By the previous claims, if $d(x)+d(y)\geq 10$, we are done by induction.  Assume $d(x)+d(y)\leq 9$.  Summing it over all the edge pairs in $G$, we have $9e\geq \sum_{xy\in E(G)}\left(d(x)+d(y)\right)=\sum_{x\in V(G)}(d(x))^2\geq n\overline{d}^2=n(\frac{2e}{n})^2$, where $\overline{d}$ is the average degree of $G$.  This gives us $e\leq \frac{9}{4}n\leq\frac{17}{7}n-2$ for $n\geq \frac{56}{5}$.

§ PLANAR TURÁN NUMBER OF S2,5

For the rest of the section let $G$ be a $n$-vertex $S_{2,5}$-free planar graph.  Notice that, since $S_{2,5}$ contains $9$ vertices, a maximal planar graph with $n\leq 8$ vertices, does not contain an $S_{2,5}$. Recall that, an $n$-vertex maximal planar graph contains $3n-6$. Since, $3n-6\leq \frac{20}{7}n$ for $n\leq 42$, Theorem <ref>(iv), holds for all $n$, $1\leq n\leq 42$.

The following claims deal with the different cases of degree pairs.

If $G$ contains a vertex $v$ of degree greater than or equal to $8$, $e(G)\leq \frac{20}{7}n.$

Let $v\in V(G)$, such that $d(v)\geq 7$.  It is easy to check that for each $u\in N(v)$, $d(u)\leq 2$, otherwise, we find a copy of $S_{2,5}$ in $G$. Delete a vertex $u\in N(v)$, then the number of deleted edges is at most $2$. By the induction hypothesis, we get $e(G-\{u\})\leq \frac{20}{7}(n-1)$. Hence, $e(G)=e(G-u)+d(u)\leq \frac{20}{7}(n-1)+2\leq\frac{20}{7}n$.

If $G$ contains a vertex $v$ of degree equal to $7$, $e(G)\leq \frac{20}{7}n.$

Let $v\in V(G)$, such that $d(v)=7$ and let $H:=N(v)\cup \{v\}$.  Suppose we delete the $8$ vertices in $H$.  It is easy to check that each $u\in N(v)$ can only have one outer edge.  Note that, if $u\in N(v)$ has an outer edge, it is not adjacent to any other $x\in N(v)$.  Hence $u$ is a degree $2$ vertex, and we are done by induction.  In the other case, the neighbors of $v$ have no outer edges.  Consider the maximum planar graph on the vertices of $H$.  The maximum number of edges deleted is $3\times 8-6=18$,  and again we are done by induction.

(x) at (-12,0);
(y) at (12,0);
(a) at (0,36);
(b) at (0,27);
(c) at (0,18);
(d) at (0,9);
(e) at (0,-9);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (x) – (e) – (y);
[fill=black] (x) circle(∘)  node[label=below:$x$] ;
[fill=black] (y) circle(∘)  node[label=below:$y$] ;
[fill=black] (a) circle(∘)  node[label=above:$a$] ;
[fill=black] (b) circle(∘)  node[label=above:$b$] ;
[fill=black] (c) circle(∘)  node[label=above:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;

$G$ has a $6-6$ edge $xy$, with $5$ triangles sitting on the edge $xy$.

If $G$ contains a $6-6$ edge, then $e(G)\leq \frac{20}{7}n.$

Let $xy\in E(G)$ be a $6$-$6$ edge. We subdivide the cases based on the number of triangles sitting on the edge $xy$.

* There are $5$ triangles sitting on the edge $xy$. Let $a,b,c,d$ and $e$ be vertices in $G$ which are adjacent to both $x$ and $y$ (see Figure <ref>).  Denote $S_1=\{a,b,c,d,e\}$ and $H=\{x,y,a,b,c,d,e\}$.  Deleting the vertices in $H$.  The vertices in $S_1$ can have one outer edge each.  The vertices in $S_1$ can form a  path of length $4$.  Hence the maximum number of edges deleted is at most $11+5_{\text{out of $S_{1}$}}+4_{\text{in $S_1$}}=20.$  Using the induction hypothesis,
$$e(G)\leq e(G-H)+20\leq \frac{20}{7}(n-7)+20=\frac{20}{7}n.$$

* There are $4$ triangles sitting on the edge $xy$.  Let $a,b,c$ and $d$ be vertices in $G$ which are adjacent to both $x$ and $y$. Let $e$ be the vertex adjacent to $x$ but not adjacent to $y$, and $f$ be the vertex adjacent to $y$ and but not adjacent to $x$.   Denote $S_1=\{a,b,c,d\}$ and $H=\{x,y\}\cup S_1\cup\{e,f\}$.  Deleting the vertices in $H$.  The vertices $e$ and $f$ can have at most one outer edge.  We differentiate the cases based on the neighbors of $e$ and $f$ as follows:

* The vertices $e$ and $f$ have no neighbors in $S_1$, see Figure <ref>(i).
The vertices in $S_1$ can have one outer edge each and can form a path of length $3$ in $S_1$.  If the vertices $e$ and $f$ are adjacent, then both of them cannot have an outer edge.  Otherwise we have an $S_{2,5}$ with $ex$ (or $fy$) as the backbone.  Hence in this case, the maximum number of edges deleted is at most $11+3_{\text{inside $S_1$}}+4_{\text{out of $S_1$}}+2_{\text{out of $e,f$}}=20$.

* One of the vertices $e$ or $f$ has one neighbor in $S_1$, and the other has none.
Without loss of generality, assume that $a$ and $e$ are adjacent (see Figure <ref>(ii)), then $a$ cannot have an outer edge.  Otherwise we have a $S_{2,5}$ with $ay$ as the backbone.  If the vertices $e$ and $f$ are adjacent, then both of them cannot have an outer edge.  Similarly  as  before,  the vertices $b,c$ and $d$ can have one outer edge each and the vertices $\{a,b,c,d\}$ can form a path of length $3$ in $S_1$.  Hence in this case, the maximum number of edges deleted is at most $12+3_{\text{in $S_1$}}+3_{\text{out of $S_1$}}+2_{\text{out of $e,f$}}=20$.

* The vertices $e$ and $f$ have one neighbor in $S_1$.
Suppose $a$ is the common neighbor of $e$ and $f$, see Figure <ref>(iii).  Similarly as before, $a$ cannot have an outer edge.  If the vertices $e$ and $f$ are adjacent, then both of them cannot have an outer edge.  The vertices $b,c$ and $d$ can  have  one  outer  edge  each  and  the  vertices $\{a,b,c,d\}$ can form  a  path of  length  $3$  in $S_1$.  Hence in this case, the maximum number of edges deleted is at most $13+3_{\text{in $S_1$}}+3_{\text{out of $S_1$}}+2_{\text{out of $e,f$}}=21$.
Suppose $a$ is the neighbor of $e$ and $d$ is the neighbor of $f$, see Figure <ref>(iv). As before, $a$ and $d$ both cannot have an outer edge.   The  vertex $b$ and $c$ can  have  one  outer  edge  and  the  vertices $\{a,b,c,d\}$ can form a  path  of  length  $3$  in $S_1$.  Thus the maximum number of edges deleted is at most $13+3_{\text{in $S_1$}}+2_{\text{out of $S_1$}}+2_{\text{out of $e,f$}}=20$.

* One of the vertices $e$ or $f$ has two neighbors in $S_1$, while the other has none.
Suppose $e$ is the neighbor of $a$ and $d$, see Figure <ref>(v). Similarly as before, $a$ and $d$ both cannot have an outer edge.  The vertices $b$ and $c$ can have one outer edge each and the vertices $\{a,b,c,d\}$ can form a path of length $3$ in $S_1$.  Thus the maximum number of edges deleted is at most $13+3_{\text{in $S_1$}}+2_{\text{out of $S_1$}}+2_{\text{out of $e,f$}}=20$.

* One of the vertices $e$ or $f$ has two neighbors in $S_1$, while the other has one neighbor.
Suppose $e$ is the neighbor of $a$ and $d$, and $f$ is the neighbor of $d$ (see Figure <ref>(vi)).  Similarly as before, $a$ and $d$ both cannot have an outer edge.  The vertices  $b$ and $c$ can have one outer edge and the vertices $\{a,b,c,d\}$ can form a path of length $3$ in $S_1$.  Thus the maximum number of edges deleted is at most $14+3_{\text{in $S_1$}}+2_{\text{out of $S_1$}}+2_{\text{out of $e,f$}}=21$.
In the other case, assume that $e$ is the neighbor of $a$ and $d$, and $f$ is the neighbor of $b$ (see Figure <ref>(vii)).  The vertices $a,b$ and $d$ cannot have an outer edge, but they along with $c$ can form a path of length $3$ in $S_1$.  The vertex $c$ can have one outer edge.  Thus the maximum number of edges deleted is at most $14+3_{\text{in $S_1$}}+1_{\text{out of $S_1$}}+2_{\text{out of $e,f$}}=20$.

* Both the vertices $e$ and $f$ have two neighbors in $S_1$.  Suppose $e$ and $f$ are neighbors of both $a$ and $d$, see Figure <ref>(viii).  Similarly as before, $a$ and $d$ both cannot have an outer edge.  The vertices $b$ and $c$ can have one outer edge each.  The vertices $\{a,b,c,d\}$ can form a path of length $3$ in $S_1$.  Thus the maximum number of edges deleted is at most $15+3_{\text{in $S_1$}}+2_{\text{out of $S_1$}}+2_{\text{out of $e,f$}}=22$.
On the other hand, assume $e$ is the neighbor of both $a$ and $d$, while $f$ is the neighbor of $a$ and $b$ (see Figure <ref>(ix)).  The vertices $a,b$ and $d$ cannot have an outer edge, but they along with $c$ can form a path of length $3$ in $S_1$. The vertex $c$ can have one outer edge.  Thus the maximum number of edges deleted is at most $15+3_{\text{in $S_1$}}+1_{\text{out of $S_1$}}+2_{\text{out of $e,f$}}=21$.
In the last case, assume $e$ is the neighbor of $a$ and $d$ both, while $f$ is the neighbor of $b$ and $c$ (see Figure <ref>(x)).  The vertices $a,b,c$ and $d$ cannot have an outer edge, but they can form a path of length $3$ in $S_1$.  Thus the maximum number of edges deleted is at most $15+3_{\text{in $S_1$}}+2_{\text{out of $e,f$}}=20$.

(x) at (-12,0);
(y) at (12,0);
(a) at (0,27);
(b) at (0,18);
(c) at (0,9);
(d) at (0,-9);
(f) at (21,0);
(e) at (-21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (x) – (e);
[thick] (y) – (f);
[fill=black] (x) circle(∘)  node[label=above:$x$] ;
[fill=black] (y) circle(∘)  node[label=above:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
[fill=black] (f) circle(∘)  node[label=below:$f$] ;
at (0,-18) $(i)$;
(x) at (-12,0);
(y) at (12,0);
(a) at (0,27);
(b) at (0,18);
(c) at (0,9);
(d) at (0,-9);
(f) at (21,0);
(e) at (-21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (x) – (e);
[thick] (y) – (f);
[thick] (a) – (e);
[fill=black] (x) circle(∘)  node[label=above:$x$] ;
[fill=black] (y) circle(∘)  node[label=above:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
[fill=black] (f) circle(∘)  node[label=below:$f$] ;
at (0,-18) $(ii)$;
(x) at (-12,0);
(y) at (12,0);
(a) at (0,27);
(b) at (0,18);
(c) at (0,9);
(d) at (0,-9);
(f) at (21,0);
(e) at (-21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (x) – (e);
[thick] (y) – (f);
[thick] (a) – (e);
[thick] (a) – (f);
[fill=black] (x) circle(∘)  node[label=above:$x$] ;
[fill=black] (y) circle(∘)  node[label=above:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
[fill=black] (f) circle(∘)  node[label=below:$f$] ;
at (0,-18) $(iii)$;
(x) at (-12,0);
(y) at (12,0);
(a) at (0,27);
(b) at (0,18);
(c) at (0,9);
(d) at (0,-9);
(f) at (21,0);
(e) at (-21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (x) – (e);
[thick] (y) – (f);
[thick] (a) – (e);
[thick] (d) – (f);
[fill=black] (x) circle(∘)  node[label=above:$x$] ;
[fill=black] (y) circle(∘)  node[label=above:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
[fill=black] (f) circle(∘)  node[label=below:$f$] ;
at (0,-18) $(iv)$;
(x) at (-12,0);
(y) at (12,0);
(a) at (0,27);
(b) at (0,18);
(c) at (0,9);
(d) at (0,-9);
(f) at (21,0);
(e) at (-21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (x) – (e);
[thick] (y) – (f);
[thick] (a) – (e);
[thick] (e) – (d);
[fill=black] (x) circle(∘)  node[label=above:$x$] ;
[fill=black] (y) circle(∘)  node[label=above:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
[fill=black] (f) circle(∘)  node[label=below:$f$] ;
at (0,-18) $(v)$;
(x) at (-12,0);
(y) at (12,0);
(a) at (0,27);
(b) at (0,18);
(c) at (0,9);
(d) at (0,-9);
(f) at (21,0);
(e) at (-21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (x) – (e);
[thick] (y) – (f);
[thick] (a) – (e);
[thick] (e) – (d);
[thick] (f) – (d);
[fill=black] (x) circle(∘)  node[label=above:$x$] ;
[fill=black] (y) circle(∘)  node[label=above:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
[fill=black] (f) circle(∘)  node[label=below:$f$] ;
at (0,-18) $(vi)$;
(x) at (-12,0);
(y) at (12,0);
(a) at (0,27);
(b) at (0,18);
(c) at (0,9);
(d) at (0,-9);
(f) at (21,0);
(e) at (-21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (x) – (e);
[thick] (y) – (f);
[thick] (a) – (e);
[thick] (e) – (d);
[thick] (f)..controls (27,0) and (27,9) ..(b);
[fill=black] (x) circle(∘)  node[label=above:$x$] ;
[fill=black] (y) circle(∘)  node[label=above:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
[fill=black] (f) circle(∘)  node[label=below:$f$] ;
at (0,-18) $(vii)$;
(x) at (-12,0);
(y) at (12,0);
(a) at (0,27);
(b) at (0,18);
(c) at (0,9);
(d) at (0,-9);
(f) at (21,0);
(e) at (-21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (x) – (e);
[thick] (y) – (f);
[thick] (a) – (e);
[thick] (e) – (d);
[thick] (f) – (d);
[thick] (f) – (a);
[fill=black] (x) circle(∘)  node[label=above:$x$] ;
[fill=black] (y) circle(∘)  node[label=above:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
[fill=black] (f) circle(∘)  node[label=below:$f$] ;
at (0,-18) $(viii)$;
(x) at (-12,0);
(y) at (12,0);
(a) at (0,27);
(b) at (0,18);
(c) at (0,9);
(d) at (0,-9);
(f) at (21,0);
(e) at (-21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (x) – (e);
[thick] (y) – (f);
[thick] (a) – (e);
[thick] (e) – (d);
[thick] (f)..controls (27,0) and (27,9) ..(b);
[thick] (f) – (a);
[fill=black] (x) circle(∘)  node[label=above:$x$] ;
[fill=black] (y) circle(∘)  node[label=above:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
[fill=black] (f) circle(∘)  node[label=below:$f$] ;
at (0,-18) $(ix)$;

(x) at (-12,0);
(y) at (12,0);
(a) at (0,27);
(b) at (0,18);
(c) at (0,9);
(d) at (0,-9);
(f) at (21,0);
(e) at (-21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (x) – (e);
[thick] (y) – (f);
[thick] (a) – (e);
[thick] (e) – (d);
[thick] (f)..controls (27,0) and (27,9) ..(b);
[thick] (f)..controls (27,0) and (27,6) ..(c);
[fill=black] (x) circle(∘)  node[label=above:$x$] ;
[fill=black] (y) circle(∘)  node[label=above:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
[fill=black] (f) circle(∘)  node[label=below:$f$] ;
at (0,-18) $(x)$;

[foo bar]$G$ has a $6-6$ edge $xy$, with $4$ triangles sitting on the edge $xy$.

* the vertices $e$ and $f$ have no neighbors in $S_1$.

* The vertex $e$ has one neighbor in $S_1$ and $f$ has none.

* The vertices $e$ and $f$ have one common neighbor in $S_1$.

* The vertices $e$ and $f$ have one distinct neighbor in $S_1$.

* The vertex $e$ has two neighbors in $S_1$ and $f$ has none.

* The vertex $e$ is the neighbor of $a$ and $d$, and $f$ is the neighbor of $d$.

* The vertex $e$ is the neighbor of $a$ and $d$, and $f$ is the neighbor of $b$.

* The vertices $e$ and $f$ are neighbors of both $a$ and $d$.

* The vertex $e$ is the neighbor of $a$ and $d$, while $f$ is the neighbor of $a$ and $b$.

* The vertex $e$ is the neighbor of $a$ and $d$, while $f$ is the neighbor of $b$ and $c$.

Using the induction hypothesis,
$$e(G)\leq e(G-H)+22\leq \frac{20}{7}(n-8)+22=\frac{20}{7}n-\frac{6}{7}.$$
This completes the proof.

Take $x,y\in V(G)$.  By the previous claims, if $d(x)+d(y)\geq 12$, we are done by induction.  Assume $d(x)+d(y)\leq 11$.  Summing it over all the edge pairs in $G$, we have $11e(G)\geq \sum_{xy\in E(G)}\left(d(x)+d(y)\right)=\sum_{x\in V(G)}(d(x))^2\geq n\overline{d}^2=n(\frac{2e(G)}{n})^2$, where $\overline{d}$ is the average degree of $G$.  This gives us $e(G)\leq \frac{11}{4}n\leq \frac{20}{7}n$, for $n\geq 1$.

§ PLANAR TURÁN NUMBER OF S3,3

Before we give proof of Theorem <ref>(v), we show for infinitely many integer values of $n$, we can construct an $n$-vertex $S_{3,3}$-free planar graph $G_n$ with $\frac{5}{2}n-5$ edges.  This is to verify that the bound we have is best up to the linear term.

Consider a planar graph $G_n$ which is obtained by joining every vertex of the maximal matching on $n-2$ vertices with two vertices. Figure <ref> (a) and (b) are constructions of $G_n$ when $n$ is even or odd respectively. It can be seen that each edge in $G_n$ is has a degree $3$ end vertex. Thus, $G_n$ is an $S_{3,3}$-free planar graph. Moreover, the number of edges in the former and  later constructions are respectively,  $e(G_n)=\frac{5}{2}n-5$ and $e(G)=\frac{5}{2}n-\frac{11}{2}$.

[thick](0,4)–(0,3)(0,2)–(0,1) (0,-4)–(0,-3)(0,-2)–(0,-1);
[thick](0,4)–(0,3)(0,2)–(0,1) (0,-4)–(0,-3)(0,-2)–(0,-1);

Extremal Constructions for the lower bound of planar Turán numbers of $S_{3,3}$

§.§ Proof of Theorem <ref>(v).

Let $G$ be an $n$-vertex $S_{3,3}$-free planar graph. Notice that, since $S_{3,3}$ contains $8$ vertices, a maximal planar graph with $n\leq 7$ vertices, does not contain an $S_{3,3}$. Recall that, an $n$-vertex maximal planar graph contains $3n-6$. Since, $3n-6\leq \frac{5}{2}n-2$ for $n\leq 8$, Theorem <ref>(v), holds for all $n$, $3\leq n\leq 8$.

From now on, we assume that $G$ contains no vertex of degree at most $2$ and no $3$-$3$ edge. Otherwise, it is easy to finish the proof by induction. The following claims help us in understanding the structure of $G$.

No vertex in $G$ with a degree at least $7$ is adjacent with a vertex of degree at least $4$.

Suppose not. Let $xy$ be an edge in $G$ such that $d(x)\geq 7$ and $d(y)\geq 4$. Obviously, there are three vertices in $V(G)\backslash \{x\}$, say $y_1,y_2$ and $y_3$, which are adjacent to $y$. Since $|N(x)\backslash\{y\}|\geq 6$, there are three vertices $x_1,x_2$ and $x_3$, not in $\{y,y_1,y_2,y_3\}$ which are adjacent to $x$. But this implies we got an $S_{3,3}$ in $G$ with backbone $xy$ and leaf-sets $\{x_1,x_2,x_3\}$ and $\{y_1,y_2,y_3\}$ respectively, which is a contradiction.
This completes the proof of Claim <ref>.

If there is a $6$-$6$ edge in $G$, then $e(G)\leq \frac{5}{2}n-2.$

Let $xy\in E(G)$ be a $6$-$6$ edge. The only possibility is that there are $5$ triangles sitting on the edge $xy$, see Figure <ref>. Otherwise, $G$ contains an $S_{3,3}$ with $xy$ as the backbone, which is a contradiction.

(x) at (-12,0);
(y) at (12,0);
(a) at (0,36);
(b) at (0,27);
(c) at (0,18);
(d) at (0,9);
(e) at (0,-9);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (x) – (e) – (y);
[fill=black] (x) circle(∘)  node[label=below:$x$] ;
[fill=black] (y) circle(∘)  node[label=below:$y$] ;
[fill=black] (a) circle(∘)  node[label=above:$a$] ;
[fill=black] (b) circle(∘)  node[label=above:$b$] ;
[fill=black] (c) circle(∘)  node[label=above:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;

$G$ has a $6-6$ edge $xy$.

Let $a,b,c,d$ and $e$ be vertices in $G$ which are adjacent to both $x$ and $y$.
Denote $S_1=\{a,b,c,d,e\}$ and $H=\{x,y,a,b,c,d,e\}$.  Deleting the vertices in $H$.  , assume $a$ has two outer edges.  We immediately get an $S_{3,3}$ with $xa$ or $ya$ as the backbone.  Thus any vertex in the set $S_1$ can have at most $1$ outer edge. If there is no edge between the vertices in $S_1$, deleting all vertices in $H$, we deleted at most $11+5_{\text{out of $S_1$}}=16$ edges.  Assume there is an edge between the vertices in $S_1$, say $ab$.  If $a$ (or $b$) has an outer edge, $xa$ (or $xb$) is the backbone of an $S_{3,3}$.  Similarly for the other inner edges in $S_1$, both the vertices cannot have an outer edge then.  Thus if $S_1$ has inner edges, the number of edges deleted is at most $11+4_{\big(\text{in $S_1$}+\text{out of $S_1$}\big)}=15$.  Using the induction hypothesis,
$$e(G)\leq e(G-H)+16\leq \frac{5}{2}(n-7)-2+16=\frac{5}{2}n-3.5<\frac{5}{2}n-2.$$
This completes the proof.

(x) at (-12,0);
(y) at (12,0);
(a) at (0,27);
(b) at (0,18);
(c) at (0,9);
(d) at (0,-9);
(e) at (21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (e) – (y);
[fill=black] (x) circle(∘)  node[label=below:$x$] ;
[fill=black] (y) circle(∘)  node[label=below:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
at (0,-21)(i);
(x) at (-12,0);
(y) at (12,0);
(a) at (0,27);
(b) at (0,18);
(c) at (0,9);
(d) at (0,-9);
(e) at (21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (e) – (y);
[thick] (e) – (a);
[fill=black] (x) circle(∘)  node[label=below:$x$] ;
[fill=black] (y) circle(∘)  node[label=below:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
at (0,-21)(ii);
(x) at (-12,0);
(y) at (12,0);
(a) at (0,27);
(b) at (0,18);
(c) at (0,9);
(d) at (0,-9);
(e) at (21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (e) – (y);
[thick] (e) – (a);
[thick] (e) – (d);
[fill=black] (x) circle(∘)  node[label=above:$x$] ;
[fill=black] (y) circle(∘)  node[label=above:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
at (0,-21)(iii);

[foo bar2]$G$ has a $5-6$ edge $xy$.

* The vertex $e$ has no neighbors in $S_1$.

* The vertex $e$ has one neighbor in $S_1$.

* The vertex $e$ has two neighbors in $S_1$.

If there is a $5$-$6$ edge in $G$, then $e(G)\leq \frac{5}{2}n-2.$

Let $xy$ be a $5$-$6$ edge in $G$.  There are $4$ triangles sitting on the edge $xy$, see Figure <ref>.  Let $a,b,c$ and $d$ be vertices in $G$ which are adjacent to both $x$ and $y$.  Let $e$ be a vertex adjacent to $y$ but not adjacent to $x$. Denote $S_1=\{a,b,c,d\}$ and $H=\{x,y,a,b,c,d,e\}$.  Delete the vertices in $H$.  Any vertex in $S_1$ can have at most $1$ outer edge.  If there is an edge joining vertices inside $S_1$, say $ab$.  Similarly, as before, the vertices $a$ and $b$ cannot have outer edges. We further distinguish the cases based on the number of inner edges from $e$ as follows:

* The vertex $e$ has no neighbors in $S_1$, see Figure <ref>(i). Clearly, $e$ can have $2$ outer edges. If there is no edge between the vertices in $S_1$, deleting all vertices in $H$, we deleted at most $10+2_{\text{out of e}}+4_{\text{out of $S_1$}}=16$ edges.  Suppose $a$ and $b$ are adjacent. Recall, both vertices $a$ and $b$ cannot have an outer edge.  Similarly, for the other edges in $S_1$, both the vertices cannot have an outer edge then.  If there are edges between the vertices in $S_1$, the number of edges deleted is at most $10+2_{\text{out of e}}+3_{\big(\text{in $S_1$}+\text{out of $S_1$}\big)}=15$.

* The vertex $e$ has one neighbor in $S_1$. Without loss of generality, let $e$ and $a$ be adjacent,  see Figure <ref>(ii).  The vertex $e$ can have only one outer edge.  If the vertex $a$ has an outer edge, we have an $S_{3,3}$ with $xa$ as the backbone.  If there is no edge between the vertices in $S_1$, deleting the vertices in $H$, we have deleted at most  $11+3_{\text{out of $S_1$}}+1_{\text{out of $e$}}=15$ edges.  Suppose $a$ and $b$ are adjacent, then $b$ cannot have an outer edge.  Similarly, for the edges in $S_1$, both the vertices cannot have an outer edge.  If there are edges between the vertices in $S_1$, the number of edges deleted is at most  $11+3_{\big(\text{in $S_1$}+\text{out of $S_1$}\big)}+1_{\text{out of $e$}}=15$.

* The vertex $e$ has two neighbors in $S_1$.  Without loss of generality, let $e$ be adjacent to both $a$ and $d$, see Figure <ref>(iii). The vertex $e$ cannot have any outer edges, otherwise we have a $S_{3,3}$ with $ye$ as the backbone.  If either $a$ or $d$ has an outer edge, we have an $S_{3,3}$ with $xa$ or $xd$ as the backbone respectively . Suppose there is no edge between the vertices in $S_1$.  Deleting the vertices in $H$, the total number of edges deleted is at most  $12+2_{\text{out of $S_1$}}=14$. Suppose $a$ and $b$ are adjacent, then $b$ cannot have an outer edge.  Similarly for other edges in $S_1$ except $ad$, which is still possible without any extra restrictions.  Thus the total number of edges deleted is at most  $12+3_{\big(\text{in $S_1$}+\text{out of $S_1$}\big)}=15$.

Thus by induction
$$e(G)=e(G-H)+16\leq \frac{5}{2}(n-7)-2+16< \frac{5}{2}n-2,$$
and we are done.

(x) at (-12,0);
(y) at (12,0);
(a) at (0,18);
(b) at (0,9);
(c) at (0,-9);
(d) at (21,6);
(e) at (21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (d) – (y);
[thick] (e) – (y);
[fill=black] (x) circle(∘)  node[label=below:$x$] ;
[fill=black] (y) circle(∘)  node[label=below:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=above:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
at (0,-18)(i);
(x) at (-12,0);
(y) at (12,0);
(a) at (0,18);
(b) at (0,9);
(c) at (0,-9);
(d) at (21,6);
(e) at (21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (d) – (y);
[thick] (d) – (a);
[thick] (e) – (y);
[fill=black] (x) circle(∘)  node[label=below:$x$] ;
[fill=black] (y) circle(∘)  node[label=below:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=above:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
at (0,-18)(ii);

(x) at (-12,0);
(y) at (12,0);
(a) at (0,18);
(b) at (0,9);
(c) at (0,-9);
(d) at (21,6);
(e) at (21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (d) – (y);
[thick] (d) – (a);
[thick] (e) – (y);
[thick](e)..controls (27,12) and (27,18) ..(a);
[fill=black] (x) circle(∘)  node[label=below:$x$] ;
[fill=black] (y) circle(∘)  node[label=below:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=above:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
at (0,-18)(iii);

(x) at (-12,0);
(y) at (12,0);
(a) at (0,18);
(b) at (0,9);
(c) at (0,-9);
(d) at (21,6);
(e) at (21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (d) – (y);
[thick] (d) – (a);
[thick] (e) – (y);
[fill=black] (x) circle(∘)  node[label=above:$x$] ;
[fill=black] (y) circle(∘)  node[label=above:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=above:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
at (0,-18)(iv);

(x) at (-12,0);
(y) at (12,0);
(a) at (0,18);
(b) at (0,9);
(c) at (0,-9);
(d) at (21,6);
(e) at (21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (d) – (y);
[thick] (d) – (a);
[thick] (e) – (y);
[thick](d)..controls (27,0) and (27,-12) ..(c);
[fill=black] (x) circle(∘)  node[label=above:$x$] ;
[fill=black] (y) circle(∘)  node[label=above:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=above:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
at (0,-18)(v);

(x) at (-12,0);
(y) at (12,0);
(a) at (0,18);
(b) at (0,9);
(c) at (0,-9);
(d) at (21,6);
(e) at (21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (d) – (y);
[thick] (d) – (a);
[thick] (e) – (y);
[thick] (e) – (c);
[thick](d)..controls (27,0) and (27,-12) ..(c);
[fill=black] (x) circle(∘)  node[label=above:$x$] ;
[fill=black] (y) circle(∘)  node[label=above:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=above:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
at (0,-18)(vi);

(x) at (-12,0);
(y) at (12,0);
(a) at (0,18);
(c) at (0,-27);
(b) at (0,-3);
(d) at (21,6);
(e) at (3,-6);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (d) – (y);
[thick] (d) – (a);
[thick] (e) – (y);
[thick] (e) – (b);
[thick](d)..controls (27,0) and (27,-12) ..(c);
[fill=black] (x) circle(∘)  node[label=above:$x$] ;
[fill=black] (y) circle(∘)  node[label=above:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=[label distance=.01cm]225:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=right:$e$] ;
at (0,-36)(vii);
(x) at (-12,0);
(y) at (12,0);
(a) at (0,18);
(c) at (0,-27);
(b) at (0,-3);
(d) at (21,6);
(e) at (3,-6);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (d) – (y);
[thick] (d) – (a);
[thick] (e) – (y);
[thick] (e) – (c);
[thick] (e) – (b);
[thick](d)..controls (27,0) and (27,-12) ..(c);
[fill=black] (x) circle(∘)  node[label=above:$x$] ;
[fill=black] (y) circle(∘)  node[label=above:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=[label distance=.01cm]225:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=right:$e$] ;
at (0,-36)(viii);

[foo bar]$G$ has a $4-6$ edge $xy$.

* The vertices $d$ and $e$ have no neighbors in $S_1$.

* The vertex $d$ has one neighbor in $S_1$, and $f$ has none.

* Both the vertices $d$ and $e$ have one common neighbor in $S_1$.

* The vertices $d$ and $e$ have one distinct neighbor in $S_1$

* One of the vertices $d$ or $e$ has two neighbors in $S_1$.

* Suppose $d$ is neighbor of $a$ and $c$, while $e$ is neighbor of $c$.

* Suppose $d$ is neighbor of $a$ and $c$, while $e$ is neighbor of $b$.

* Both the vertices $d$ and $e$ have two neighbors in $S_1$.

If there is a $4$-$6$ edge in $G$, then $e(G)\leq \frac{5}{2}n-2.$

The only possibility is three triangles sitting on the edge $xy$, see Figure <ref>.  Let $a,b$ and $c$ be vertices in $G$ which are adjacent to both $x$ and $y$. Let $d$ and $e$ be a vertices adjacent to $y$ but not to $x$. Denote $S_1=\{a,b,c\}$ and $H=\{x,y,a,b,c,d,e\}$.  Delete the vertices in $H$.

The vertices $d$ and $e$ can have two outer edges each.  The vertices in $S_1$ can have one outer edge each.

* The vertices $d$ and $e$ have no neighbors in $S_1$, see Figure <ref>(i)).
If the vertices $d$ and $e$ are adjacent, then both of them can have only one outer edge.  Otherwise we have an $S_{3,3}$ with $dy$ (or $ey$) as the backbone.  If there is no edge between the vertices in $S_1$, the maximum number of edges deleted is at most $9+3_{\text{out of $S_1$}}+4_{\text{out of $d,e$}}=16$.  If there are edges between the vertices in $S_1$, the maximum number of edges deleted is at most $9+2_{\big(\text{in $S_1$}+\text{out of $S_1$}\big)}+4_{\text{out of $d,e$}}=15$.

* One of the vertices $d$ or $e$ has one neighbor in $S_1$, while the other has none.
Assume that $d$ and $a$ are adjacent (see Figure <ref>(ii)).  The vertex $a$ cannot have an outer edge, and $d$ has only one outer edge.  If the vertices $d$ and $e$ are adjacent, then $d$ cannot have an outer edge and $e$ can have only one outer edge.  Otherwise we have an $S_{3,3}$ with $dy$ (or $ey$) as the backbone.  If there is no edge between the vertices in $S_1$, the maximum number of edges deleted is at most $10+2_{\text{out of $S_1$}}+3_{\text{out of $d,e$}}=15$.  If $a$ and $b$ (or $c$) are adjacent, then $b$ (or $c$) does not have an outer edge.  Otherwise, we find an $S_{3,3}$ with $yb$ (or $yc$) as the backbone.  Similarly for the inner edge $bc$.  If there are edges between the vertices in $S_1$, the maximum number of edges deleted is at most $10+2_{\big(\text{in $S_1$}+\text{out of $S_1$}\big)}+3_{\text{out of $d,e$}}=15$.

* Both the vertices $d$ and $e$ have one neighbor in $S_1$.
Suppose $a$ is the common neighbor of $d$ and $e$ (see Figure <ref>(iii)).  Similarly as before, $a$ cannot have an outer edge, and $d$ and $e$ can have one outer edge each.  If the vertices $d$ and $e$ are adjacent, $d$ and $e$ have no outer edges.  If there is no edge between the vertices in $S_1$, the maximum number of edges deleted is at most $11+2_{\text{out of $S_1$}}+2_{\text{out of $d,e$}}=15$.   If $a$ and $b$ (or $c$) are adjacent, then $b$ (or $c$) does not have an outer edge.  Otherwise, we find an $S_{3,3}$ with $yb$ (or $yc$) as the backbone.  Similarly for the inner edge $bc$.  If there are edges between the vertices in $S_1$, the maximum number of edges deleted is at most $11+2_{\big(\text{in $S_1$}+\text{out of $S_1$}\big)}+2_{\text{out of $d,e$}}=15$.  Suppose $a$ is the neighbor of $d$ and $c$ is the neighbor of $e$ (see Figure <ref>(iv)). Similarly as before, $a$ and $c$ both cannot have an outer edge, and $d$ and $e$ can have one outer edge each.  If the vertices $d$ and $e$ are adjacent, then both of them have no outer edges.  If there is no edge between the vertices in $S_1$, the maximum number of edges deleted is at most $11+1_{\text{out of $S_1$}}+2_{\text{out of $d,e$}}=14$.   If $a$ and $b$ are adjacent, then $b$ does not have an outer edge.  Similarly for the inner edge $bc$.  The vertices $a$ and $c$ can be adjacent without any other constraints.  If there are edges between the vertices in $S_1$, the maximum number of edges deleted is at most $11+2_{\big(\text{in $S_1$}+\text{out of $S_1$}\big)}+2_{\text{out of $d,e$}}=15$.

* One of the vertices $d$ or $e$ has two neighbors in $S_1$, while the other has none.  Suppose $d$ is neighbor of $a$ and $c$, while $e$ has no neighbors in $S_1$ (see Figure <ref>(v)).  The vertex $d$ does not have any outer edge.  Similarly as before, the vertices $a$ and $c$ cannot have an outer edge, whereas $e$ can have two outer edges.  If $d$ and $e$ are adjacent, then $e$ can have only one outer edge.  If there is no edge between the vertices in $S_1$, the maximum number of edges deleted is at most $11+1_{\text{out of $S_1$}}+2_{\text{out of $e$}}=14$.  If $a$ and $b$ are adjacent, then $b$ does not have an outer edge.  Similarly for the inner edge $bc$.  The vertices $a$ and $c$ can be adjacent without any other constraints.  If there are edges between the vertices in $S_1$, the maximum number of edges deleted is at most $11+2_{\big(\text{in $S_1$}+\text{out of $S_1$}\big)}+2_{\text{out of $e$}}=15$.

* One of the vertices $d$ or $e$ has two neighbors in $S_1$, while the other has one.
Suppose $d$ is neighbor of $a$ and $c$, while $e$ is neighbor of $c$ (see Figure <ref>(vi)).  Similarly as before, the vertices $a,c$ and $d$ cannot have an outer edge, whereas $e$ can have one outer edge.  If $d$ and $e$ are adjacent, then $e$ cannot have an one outer edge.  If there is no edge between the vertices in $S_1$, the maximum number of edges deleted is at most $12+1_{\text{out of $S_1$}}+1_{\text{out of $e$}}=14$.  In the other case, the vertices $a$ and $c$ can be adjacent without any other constraints.  If $a$ (or $c$) and $b$ are adjacent, then $b$ does not have an outer edge.  If there are edges between the vertices in $S_1$, the maximum number of edges deleted is at most $12+2_{\big(\text{in $S_1$}+\text{out of $S_1$}\big)}+1_{\text{out of $e$}}=15$.
Suppose $d$ is neighbor of $a$ and $c$, while $e$ is neighbor of $b$ (see Figure <ref>(vii)).  Similarly as before, the vertices $a,b,c$ and $d$ cannot have an outer edge, whereas $e$ can have one outer edge.  If $d$ and $e$ are adjacent, then $e$ cannot have an one outer edge.  If there is no edge between the vertices in $S_1$, the maximum number of edges deleted is at most $12+1_{\text{out of $e$}}=13$.  In the other case, the vertices $a,b$ and $c$ can be adjacent without any other constraints.  Hence, the maximum number of edges deleted is at most $12+2_{\text{in $S_1$}}+1_{\text{out of $e$}}=15$.

* Both the vertices $d$ and $e$ have two neighbors in $S_1$.
Suppose $d$ is neighbor of $a$ and $c$, while $e$ is neighbor of $b$ and $c$ (see Figure <ref>(viii)).  Similarly as before, the vertices $a, b, c, d$ and $e$ cannot have an outer edge.  The vertex $c$ can be adjacent to $a$ and $b$ without any other constraints.  Hence, the maximum number of edges deleted is at most $13+2_{ac, bc}=15$.

Thus by induction
$$e(G)=e(G-H)+15\leq \frac{5}{2}(n-7)-2+15=\frac{5}{2}n-4.5< \frac{5}{2}n-2,$$
and we are done.

The following lemma completes proof of the theorem.

If $G$ contains no $4$-$6$, $5$-$6$ and $6$-$6$ edge, then $e(G)\leq \frac{5}{2}n-2.$

$A=\{x\in V(G)\ | \ d(x)=3\}$, $B=\{x\in V(G)\ | \ d(x)=4 \ \text{or} \ d(y)=5\}$ and   $C=\{x\in V(G)\ |\ d(x)\geq 6\}.$

Since there is no $3$-$3$ edge, the vertices in $A$ are independent. From Claim <ref> and <ref>, there is no edge between the sets $B$ and $C$. Moreover, no edge joins any two vertices in $C$ by Claim <ref>. Figure <ref> shows distribution of the edges in $G$.

[rotate around=90:(0,-7.5), thick,red] (0,-7.5) ellipse (23 and 9);
[rotate around=90:(-30,-7.5), thick, red] (-30,-7.5) ellipse (23 and 9);
[rotate around=90:(30,-7.5),  thick,red] (30,-7.5) ellipse (23 and 9);
[thick](-30,10)..controls (-35, 7) and (-35,3) ..(-30,0);
[thick](-30,10)..controls (-25, 5) and (-25,-5) ..(-30,-10);
[thick](-30,-10)..controls (-25, -13) and (-25,-20) ..(-30,-25);
[thick](-30,0)..controls (-35, -3) and (-35,-7) ..(-30,-10);
at (0,20) $A$;
at (-30,20) $B$;
at (30,20) $C$;

A graph showing the distribution of edges in $G$.

Let $|A|=a, |B|=b$ and $|C|=c$. Let $x$ be the number of edges between the sets $A$ and $B$, i.e, $e(A,B)=x$. Since the maximum degree in $B$ is $5$,  we have $2e(G[B])=\sum_{v\in B}d(v)-x$ which implies $e(G)\leq \frac{5b-x}{2}$. Since degree of each vertex in $A$ is $3$ and vertices in $A$ are independent, $e(A,C)= 3a-x$. Thus, the number of edges in $G$ is

\begin{align*}
e(G)=e(G[B])+e(A,B)+e(A,C)\leq \frac{5b-x}{2}+x+3a-x=\frac{5}{2}a+\frac{5}{2}b+\frac{a-x}{2}.
\end{align*}

On the other hand, since  $G$ is planar and the graph induced by vertices in $A$ and vertices in $C$ is bipartite, $e(A,C)=3a-x\leq 2(a+c)-4$. This implies that $\frac{a-x}{2}\leq c-2= \frac{5}{2}c-\frac{3}{2}c-2$ for all $c\geq 0$. Therefore, using the inequality in (<ref>), we get

\begin{align}\label{eq1}
e(G)\leq \frac{5}{2}a+\frac{5}{2}b+\frac{5}{2}c-\left(\frac{3}{2}c+2\right)=\frac{5}{2}(a+b+c)-\left(\frac{3}{2}c+2\right)\leq\frac{5}{2}n-2.
\end{align}

Notice that, the last inequality in (<ref>) holds (and hence Claim <ref>) if $a\neq 0$ and $c\neq 0$. To finish the proof we distinguish the following two cases.
$a\neq 0$ and $c=0$.

Observe that $e(G)\leq \frac{5(n-a)+3a}{2}=\frac{5}{2}n-a$. Hence if $a\geq 2$, then we are done. Thus, $a=1$. Let the number of degree $4$ vertices in $G$ be $k$. Hence, $e(G)= \frac{5(n-k-1)+4k+3}{2}=\frac{5}{2}n-\frac{k}{2}-1$. Hence if $k\geq 2$, then we are done.

Let the number of degree $4$ vertices in $G$ be at most 1. Let $A=\{x\}$ and $N(x)=\{x_1,x_2,x_3\}$. Let $d(x_i)=5$, $i\in[3]$. Considering that there is at most one degree 4 vertex in $G$ it is easy to find a degree $5$ vertex in $\cup_{i=1}^{3}N(x_i)$ such that all its $5$ neighbours are with degree 5. Moreover, the same property holds if one  vertex in $N(x)$ be of degree 4. Let $v$ be a degree $5$ vertex in $G$ such that all its $5$ neighbouring vertices are of degree 5. Let $N(v)=\{x_1,x_2,x_3,x_4,x_5\}$ and a plane drawing of $G$ results a clockwise alignment $x_1,x_2,x_3,x_4,x_5$ about $v$. Since $G$ is an $S_{3,3}$-free graph, every $5$-$5$ edge in $G$ must be contained in at least 3 triangles. Thus an edge $x_1v$ must be contained in at least $3$ triangles. But this implies, $x_1$ must be adjacent with at least with one vertex in $\{x_3,x_4\}$. Without loss of generality, assume $x_1$ and $x_3$ are adjacent. Then the $5$-$5$ edge $x_2v$ is contained in at most $2$ triangles, which results an $S_{3,3}$ in $G$ with $x_2v$ as the backbone.

Let the number of degree $4$ vertices in $G$ be $k$. Then $e(G)=\frac{5(n-k)+4k}{2}=\frac{5}{2}n-\frac{k}{2}$. If the number of degree $4$ vertices is at least $4$, then $e(G)\leq \frac{5}{2}n-2$ and we are done. Now assume that the number of degree $4$ vertices in $G$ is at most $3$. Notice that $v(G)\geq 8$, otherwise, taking any maximal planar graph on $n$ vertices, it can be checked that $3n-6<\frac{5}{2}n-2$.

Let $v$ be a degree $5$ vertex in $G$ and let $N(v)=\{x_1,x_2,x_3,x_4,x_5\}$. Notice that at least two vertices in $N(v)$ must be of degree $5$, otherwise the number of degree $4$ vertices is at least $4$ and we are done. Let the plane drawing of $G$ results the vertices in $N(v)$ aligned in clockwise direction as $x_1,x_2,x_3,x_4,x_5$.

We claim that there are exactly $2$ vertices in $N(v)$ which are of degree $5$. Indeed, suppose that the number of degree $5$ vertices is at least $3$. Hence we can assume that for some $i\in [5]$, $d(x_i)=d(x_{i+1})=5$. Without loss of generality assume that this vertices are $x_1$ and $x_2$. Since $x_1v$ and $x_2v$ are $5$-$5$ edges, then they must be contained in at least $3$ triangles. Hence both $x_1$ and $x_2$ must be adjacent with $x_4$. On the other hand, it is easy to see that $x_3v$ and $x_5v$ are $4$-$5$ edges. Thus $x_3$ must be adjacent with $x_2$ and $x_4$, and similarly $x_5$ must be adjacent with $x_1$ and $x_4$.  Since $d(x_3)=4$, then there must be a vertex $x_6$, such that $x_3x_6\in E(G)$. If $d(x_6)=5$, then clearly $x_6$ must be adjacent with $x_4$ which is impossible as $d(x_4)=5$. Hence $d(x_6)=4$. With similar argument we have another vertex $x_7$ adjacent with $x_5$ and $d(x_7)=4$. This is a contradiction as the number of degree $4$ vertices in $G$ is at least $4$. Namely, $x_3,x_5,x_6$ and $x_7$.

So we have an assumption that only two vertices in $N(v)$ are of degree $5$. Moreover, we need to assume that the vertices are not consecutive with respect to the alignment in clockwise direction. Without loss of generality assume the vertices are $x_2$ and $x_4$. It can be checked that $x_2$ and $x_4$ are adjacent. Since $x_1v$ and $x_5v$ are $4$-$5$ edges, then $x_1x_2,x_1x_5$ and $x_5x_4$ are in $G$. Since  $d(x_3)=4$, there must exist a vertex $x_6$ adjacent to the vertex $x_3$. If this vertex is of degree $4$, then it is a contradiction as we found $4$ vertices of degree $4$, namely $x_1,x_3,x_5$ and $x_6$. Hence $d(x_6)=5$ and $x_2x_6$ and $x_4x_6$ are in $G$. Since $x_1$ is with degree $4$, there must exist a vertex $x_7$ such that $x_1x_7\in E(G)$. If $d(x_7)$ is $5$, then we are done as $x_7$ is adjacent with $x_2$ and $d(x_2)\geq 6$, which is a contradiction. Hence $x_7$ must be with degree $4$. But this is a contradiction as we found $4$ vertices of degree $4$, namely $x_1,x_3,x_5$ and $x_7$. This completes the proof of Claim <ref>, and subsequently the proof of Theorem <ref>(v).

§ PLANAR TURÁN NUMBER OF S3,4

For the rest of the section let $G$ be a $n$-vertex $S_{3,4}$-free planar graph.  Notice that, since $S_{3,4}$ contains $9$ vertices, a maximal planar graph with $n\leq 8$ vertices, does not contain an $S_{3,4}$. Recall that, an $n$-vertex maximal planar graph contains $3n-6$. Since, $3n-6\leq \frac{20}{7}n$ for $n\leq 42$, Theorem <ref>(vi), holds for all $n$, $1\leq n\leq 42$.

No vertex in $G$ with a degree at least $8$ is adjacent with a vertex of degree at least $4$.

Suppose not. Let $xy$ be an edge in $G$ such that $d(x)\geq 8$ and $d(y)\geq 4$. Obviously, there are three vertices in $V(G)\backslash \{x\}$, say $y_1,y_2$ and $y_3$, which are adjacent to $y$. Since $|N(x)\backslash\{y\}|\geq 7$, there are four vertices $x_1,x_2,x_3$ and $x_4$, not in $\{y,y_1,y_2,y_3\}$ which are adjacent to $x$. But this implies we got an $S_{3,4}$ in $G$ with backbone $xy$ and leaf-sets $\{x_1,x_2,x_3,x_4\}$ and $\{y_1,y_2,y_3\}$ respectively, which is a contradiction.   This completes the proof.

(x) at (-12,0);
(y) at (12,0);
(a) at (0,36);
(b) at (0,27);
(c) at (0,18);
(d) at (0,9);
(e) at (0,-9);
(f) at (0,-18);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (x) – (e) – (y);
[thick] (x) – (f) – (y);
[fill=black] (x) circle(∘)  node[label=below:$x$] ;
[fill=black] (y) circle(∘)  node[label=below:$y$] ;
[fill=black] (a) circle(∘)  node[label=above:$a$] ;
[fill=black] (b) circle(∘)  node[label=above:$b$] ;
[fill=black] (c) circle(∘)  node[label=above:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
[fill=black] (f) circle(∘)  node[label=below:$f$] ;

(x) at (-12,0);
(y) at (12,0);
(a) at (0,36);
(b) at (0,27);
(c) at (0,18);
(d) at (0,9);
(e) at (0,-9);
(f) at (21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (x) – (e) – (y);
[thick] (f) – (y);
[fill=black] (x) circle(∘)  node[label=below:$x$] ;
[fill=black] (y) circle(∘)  node[label=below:$y$] ;
[fill=black] (a) circle(∘)  node[label=above:$a$] ;
[fill=black] (b) circle(∘)  node[label=above:$b$] ;
[fill=black] (c) circle(∘)  node[label=above:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
[fill=black] (f) circle(∘)  node[label=below:$f$] ;
at (0,-30) $(ii)$;

(x) at (-12,0);
(y) at (12,0);
(a) at (0,27);
(b) at (0,18);
(c) at (0,9);
(d) at (0,-9);
(f) at (21,0);
(e) at (21,6);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (e) – (y);
[thick] (f) – (y);
[fill=black] (x) circle(∘)  node[label=below:$x$] ;
[fill=black] (y) circle(∘)  node[label=below:$y$] ;
[fill=black] (a) circle(∘)  node[label=above:$a$] ;
[fill=black] (b) circle(∘)  node[label=above:$b$] ;
[fill=black] (c) circle(∘)  node[label=above:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
[fill=black] (f) circle(∘)  node[label=below:$f$] ;
at (0,-30) $(ii)$;

[foo bar] The various possibilities for a degree $7$ vertex, in the case of $S_{3,4}$ free graphs

* Structure of a $7$-$7$ edge $xy$.

* Structure of a $6$-$7$ edge $xy$.

* Structure of a $5$-$7$ edge $xy$.

$G$ has a $7-7$ edge $xy$.

If there is a $7$-$7$ edge in $G$, then $e(G)\leq \frac{20}{7}n$.

Let $xy\in E(G)$ be a $7$-$7$ edge.  Since $G$ is a $S_{3,4}$ free graph, there are $6$ triangles sitting on the edge $xy$ and denote the third vertex of the triangles by $\{a,b,c,d,e,f\}$ (see Figure <ref>(i)).  Denote $S_1=\{a,b,c,d,e,f\}$ and $H=\{x,y,a,b,c,d,e,f\}$.   Deleting the vertices in $H$.  , assume $a$ has two outer edges.  We immediately get an $S_{3,4}$ with $xa$ or $ya$ as the backbone.  Thus any vertex in the set $S_1$ can have at most $1$ outer edge.
If there is no edge between the vertices in $S_1$, deleting all vertices in $H$, we deleted at most $13 + 6_{\text{out of $S_1$}} = 19$ edges. Assume there is an edge between the vertices in $S_1$, say $ab$. If $a$ (or $b$) has an outer edge, $xa$ (or $xb$) is the backbone of an $S_{3,3}$. Similarly for the other inner edges in $S_1$, both the vertices cannot have an outer edge
then. Thus if $S_1$ has inner edges, the number of edges deleted is at most $13 + 5_{\big( \text{in $S_1$+out of $S_1$}\big)}= 18$.  By the induction hypothesis, we get $e(G-H)\leq \frac{20}{7}(n-8)$. Hence, $e(G)=e(G-H)+19\leq \frac{20}{7}(n-8)+19\leq\frac{20}{7}n$.

(x) at (-15,0);
(y) at (15,0);
(a) at (0,36);
(b) at (0,27);
(c) at (0,18);
(d) at (0,9);
(e) at (0,-9);
(f) at (24,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (x) – (e) – (y);
[thick] (f) – (y);
[fill=black] (x) circle(∘)  node[label=below:$x$] ;
[fill=black] (y) circle(∘)  node[label=below:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=below:$d$] ;
[fill=black] (e) circle(∘)  node[label=above:$e$] ;
[fill=black] (f) circle(∘)  node[label=below:$f$] ;
at (0,-21)(i);
(x) at (-15,0);
(y) at (15,0);
(a) at (0,36);
(b) at (0,27);
(c) at (0,18);
(d) at (0,9);
(e) at (0,-9);
(f) at (24,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (x) – (e) – (y);
[thick] (f) – (y);
[thick] (f) – (a);
[fill=black] (x) circle(∘)  node[label=below:$x$] ;
[fill=black] (y) circle(∘)  node[label=below:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=below:$d$] ;
[fill=black] (e) circle(∘)  node[label=above:$e$] ;
[fill=black] (f) circle(∘)  node[label=below:$f$] ;
at (0,-21)(ii);
(x) at (-15,0);
(y) at (15,0);
(a) at (0,36);
(b) at (0,27);
(c) at (0,18);
(d) at (0,9);
(e) at (0,-9);
(f) at (24,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (x) – (e) – (y);
[thick] (f) – (y);
[thick] (f) – (a);
[thick] (f) – (e);
[fill=black] (x) circle(∘)  node[label=below:$x$] ;
[fill=black] (y) circle(∘)  node[label=above:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=below:$d$] ;
[fill=black] (e) circle(∘)  node[label=above:$e$] ;
[fill=black] (f) circle(∘)  node[label=below:$f$] ;
at (0,-21)(iii);

[foo bar2]$G$ has a $6-7$ edge $xy$.

* The vertex $f$ has no neighbors in $S_1$.

* The vertex $f$ has one neighbor in $S_1$.

* The vertex $f$ has two neighbors in $S_1$.

If there is a $6$-$7$ edge in $G$, then $e(G)\leq \frac{20}{7}n$.

Let $xy\in E(G)$ be a $6$-$7$ edge.  If at-most $4$ triangles are sitting on the edge $xy$, we get an $S_{3,4}$ with $xy$ as the backbone.  The only possible structure left is when there are $5$ triangles sitting on the edge $xy$. Let $a,b,c,d$ and $e$ be vertices in $G$ which are adjacent to both $x$ and $y$. Let $f$ be a vertex adjacent to $y$ but not to $x$, see Figure <ref>. Denote $S_1=\{a,b,c,d,e\}$ and $H=\{x,y,a,b,c,d,e,f\}$.  Delete the vertices in $H$.   Any vertex in $S_1$ can have at most $1$ outer edge.  If there is an edge joining vertices inside $S_1$, say $ab$.  Similarly, as before, the vertices $a$ and $b$ cannot have outer edges. We further distinguish the cases based on the number of inner edges from $f$ as follows:

* The vertex $f$ has no neighbors in $S_1$, see Figure <ref>(i). Clearly, $f$ can have $2$ outer edges. If there is no edge between the vertices in $S_1$, deleting all vertices in $H$, we deleted at most $12+2_{\text{out of f}}+5_{\text{out of $S_1$}}=19$ edges.  Suppose $a$ and $b$ are adjacent. Recall, both vertices $a$ and $b$ cannot have an outer edge.  Similarly, for the other edges in $S_1$, both the vertices cannot have an outer edge then.  Thus if $S_1$ has inner edges, the number of edges deleted is at most $12+2_{\text{out of f}}+4_{\big(\text{in $S_1$}+\text{out of $S_1$}\big)}=18$.

* The vertex $f$ has one neighbor in $S_1$. Without loss of generality, let it be $fa$,  see Figure <ref>(ii).  The vertex $f$ can have only one outer edge.  If the vertex $a$ has an outer edge, we have an $S_{3,4}$ with $xa$ as the backbone.  If there is no edge between the vertices in $S_1$, deleting the vertices in $H$, we have deleted at most  $13+4_{\text{out of $S_1$}}+1_{\text{out of f}}=18$ edges.  Suppose $a$ and $b$ are adjacent, then $b$ cannot have an outer edge.  Similarly, for the edges in $S_1$, both the vertices cannot have an outer edge.  If there are edges between the vertices in $S_1$, the number of edges deleted is at most  $13+4_{\big(\text{in $S_1$}+\text{out of $S_1$}\big)}+1_{\text{out of $e$}}=18$.

* The vertex $f$ has two neighbors in $S_1$.  Without loss of generality, let the inner edges be $af$ and $ef$, see Figure <ref>(iii). The vertex $f$ cannot have any outer edges, otherwise we have a $S_{3,4}$ with $yf$ as the backbone.  If either $a$ or $e$ has an outer edge, we have an $S_{3,4}$ with $xa$ or $xe$ as the backbone respectively . Suppose there is no edge between the vertices in $S_1$.  Deleting the vertices in $H$, the total number of edges deleted is at most  $14+3_{\text{out of $S_1$}}=17$. Suppose $a$ and $b$ are adjacent, then $b$ cannot have an outer edge.  Similarly for other edges in $S_1$ except $ad$, which is still possible without any extra restrictions.  Thus the total number of edges deleted is at most  $14+4_{\big(\text{in $S_1$}+\text{out of $S_1$}\big)}=18$.

Thus by induction
$$e(G)=e(G-H)+19\leq \frac{20}{7}(n-8)+19< \frac{20}{7}n,$$
and we are done.

(x) at (-12,0);
(y) at (12,0);
(a) at (0,27);
(b) at (0,18);
(c) at (0,9);
(d) at (0,-9);
(e) at (21,6);
(f) at (21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (e) – (y);
[thick] (f) – (y);
[fill=black] (x) circle(∘)  node[label=below:$x$] ;
[fill=black] (y) circle(∘)  node[label=below:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
[fill=black] (f) circle(∘)  node[label=below:$f$] ;
at (0,-18)(i);
(x) at (-12,0);
(y) at (12,0);
(a) at (0,27);
(b) at (0,18);
(c) at (0,9);
(d) at (0,-9);
(e) at (21,6);
(f) at (21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (e) – (y);
[thick] (e) – (y);
[thick] (e) – (a);
[thick] (f) – (y);
[fill=black] (x) circle(∘)  node[label=below:$x$] ;
[fill=black] (y) circle(∘)  node[label=below:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=right:$e$] ;
[fill=black] (f) circle(∘)  node[label=below:$f$] ;
at (0,-18)(ii);

(x) at (-12,0);
(y) at (12,0);
(a) at (0,27);
(b) at (0,18);
(c) at (0,9);
(d) at (0,-9);
(e) at (21,6);
(f) at (21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (e) – (y);
[thick] (e) – (a);
[thick] (f) – (y);
[thick](f)..controls (27,12) and (27,18) ..(a);
[fill=black] (x) circle(∘)  node[label=below:$x$] ;
[fill=black] (y) circle(∘)  node[label=below:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=left:$e$] ;
[fill=black] (f) circle(∘)  node[label=below:$f$] ;
at (0,-18)(iii);

(x) at (-12,0);
(y) at (12,0);
(a) at (0,27);
(b) at (0,18);
(c) at (0,9);
(d) at (0,-9);
(e) at (21,6);
(f) at (21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (e) – (y);
[thick] (e) – (a);
[thick] (f) – (y);
[fill=black] (x) circle(∘)  node[label=above:$x$] ;
[fill=black] (y) circle(∘)  node[label=above:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
[fill=black] (f) circle(∘)  node[label=below:$f$] ;
at (0,-18)(iv);

(x) at (-12,0);
(y) at (12,0);
(a) at (0,27);
(b) at (0,18);
(c) at (0,9);
(d) at (0,-9);
(e) at (21,6);
(f) at (21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (e) – (y);
[thick] (e) – (a);
[thick] (f) – (y);
[thick](e)..controls (27,0) and (27,-12) ..(d);
[fill=black] (x) circle(∘)  node[label=above:$x$] ;
[fill=black] (y) circle(∘)  node[label=above:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
[fill=black] (f) circle(∘)  node[label=below:$f$] ;
at (0,-18)(v);

(x) at (-12,0);
(y) at (12,0);
(a) at (0,27);
(b) at (0,18);
(c) at (0,9);
(d) at (0,-9);
(e) at (21,6);
(f) at (21,0);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (e) – (y);
[thick] (e) – (a);
[thick] (f) – (y);
[thick] (f) – (d);
[thick](e)..controls (27,0) and (27,-12) ..(d);
[fill=black] (x) circle(∘)  node[label=above:$x$] ;
[fill=black] (y) circle(∘)  node[label=above:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=above:$d$] ;
[fill=black] (e) circle(∘)  node[label=below:$e$] ;
[fill=black] (f) circle(∘)  node[label=below:$f$] ;
at (0,-18)(vi);

(x) at (-12,0);
(y) at (12,0);
(a) at (0,18);
(b) at (0,9);
(c) at (0,-3);
(d) at (0,-36);
(e) at (21,6);
(f) at (3,-6);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (e) – (y);
[thick] (e) – (a);
[thick] (f) – (y);
[thick] (f) – (c);
[thick](e)..controls (27,0) and (27,-12) ..(d);
[fill=black] (x) circle(∘)  node[label=above:$x$] ;
[fill=black] (y) circle(∘)  node[label=above:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=below:$d$] ;
[fill=black] (e) circle(∘)  node[label=right:$e$] ;
[fill=black] (f) circle(∘)  node[label=right:$f$] ;
at (0,-45)(vii);
(x) at (-12,0);
(y) at (12,0);
(a) at (0,18);
(b) at (0,9);
(c) at (0,-3);
(d) at (0,-36);
(e) at (21,6);
(f) at (3,-6);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (e) – (y);
[thick] (e) – (a);
[thick] (f) – (y);
[thick] (f) – (c);
[thick] (f) – (d);
[thick](e)..controls (27,0) and (27,-12) ..(d);
[fill=black] (x) circle(∘)  node[label=above:$x$] ;
[fill=black] (y) circle(∘)  node[label=above:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=below:$d$] ;
[fill=black] (e) circle(∘)  node[label=right:$e$] ;
[fill=black] (f) circle(∘)  node[label=right:$f$] ;
at (0,-45)(viii);
(x) at (-12,0);
(y) at (12,0);
(a) at (0,9);
(b) at (0,-3);
(c) at (0,-27);
(d) at (0,-36);
(e) at (21,6);
(f) at (3,-6);
[thick] (x) – (a) – (y) – (x);
[thick] (x) – (b) – (y);
[thick] (x) – (c) – (y);
[thick] (x) – (d) – (y);
[thick] (e) – (y);
[thick] (e) – (a);
[thick] (f) – (y);
[thick] (f) – (c);
[thick] (f) – (b);
[thick](e)..controls (27,0) and (27,-12) ..(d);
[fill=black] (x) circle(∘)  node[label=above:$x$] ;
[fill=black] (y) circle(∘)  node[label=above:$y$] ;
[fill=black] (a) circle(∘)  node[label=below:$a$] ;
[fill=black] (b) circle(∘)  node[label=below:$b$] ;
[fill=black] (c) circle(∘)  node[label=below:$c$] ;
[fill=black] (d) circle(∘)  node[label=below:$d$] ;
[fill=black] (e) circle(∘)  node[label=right:$e$] ;
[fill=black] (f) circle(∘)  node[label=right:$f$] ;
at (0,-45)(ix);

[foo bar]$G$ has a $5-7$ edge $xy$.

* The vertices $e$ and $f$ have no neighbors in $S_1$.

* The vertex $e$ has one neighbor in $S_1$, and $f$ has none.

* Both the vertices $e$ and $f$ have one common neighbor in $S_1$.

* The vertices $e$ and $f$ have one neighbor in $S_1$ and they are distinct.

* One of the vertices $e$ or $f$ has two neighbors in $S_1$.

* Suppose $e$ is neighbor of $a$ and $d$, while $f$ is neighbor of $d$.

* Suppose $e$ is neighbor of $a$ and $d$, while $f$ is neighbor of $c$.

* Suppose $e$ is neighbor of $a$ and $d$, while $f$ is neighbor of $c$ and $d$.

* Suppose $e$ is neighbor of $a$ and $d$, while $f$ is neighbor of $b$ and $c$.

If there is a $5$-$7$ edge in $G$, then $e(G)\leq \frac{20}{7}n$.

Let $xy$ be a $5-7$ edge in $G$.  Since $G$ is a $S_{3,4}$ free graph, the only possibility is four triangles sitting on the edge $xy$.  Let $a,b,c$ and $d$ be vertices in $G$ which are adjacent to both $x$ and $y$.  Let $e$ and $f$ be a vertices adjacent to $y$ but not to $x$, see Figure <ref>.   Denote $S_1=\{a,b,c,d\}$ and $H=\{x,y,a,b,c,d,e,f\}$.  Delete the vertices in $H$.

The vertices $e$ and $f$ can have two outer edges each.  The vertices in $S_1$ can have one outer edge each.  If there is an edge joining vertices inside $S_1$, say $ab$.  Similarly, as before, the vertices $a$ and $b$ cannot have outer edges.

* The vertices $e$ and $f$ have no neighbors in $S_1$, see Figure <ref>(i)).
If the vertices $e$ and $f$ are adjacent, then both of them can have only one outer edge.  Otherwise we have an $S_{3,4}$ with $ey$ (or $fy$) as the backbone.  If there is no edge between the vertices in $S_1$, the maximum number of edges deleted is at most $11+4_{\text{out of $S_1$}}+4_{\text{out of $e,f$}}=19$.  If there are edges between the vertices in $S_1$, the maximum number of edges deleted is at most $11+3_{\big(\text{in $S_1$}+\text{out of $S_1$}\big)}+4_{\text{out of $e,f$}}=18$.

* One of the vertices $e$ or $f$ has one neighbor in $S_1$, while the other has none.
Assume that $e$ and $a$ are adjacent (see Figure <ref>(ii)).  The vertex $a$ cannot have an outer edge, and $e$ has only one outer edge.  If the vertices $e$ and $f$ are adjacent, then $e$ cannot have an outer edge and $f$ can have only one outer edge.  If there is no edge between the vertices in $S_1$, the maximum number of edges deleted is at most $12+3_{\text{out of $S_1$}}+3_{\text{out of $e,f$}}=18$.   If $a$ and $b$ are adjacent, then $b$ does not have an outer edge.  Otherwise, we find an $S_{3,4}$ with $yb$ as the backbone.  Similarly for the other edges in $S_1$.  Hence in this case, the maximum number of edges deleted is at most $12+3_{\big(\text{in $S_1$}+\text{out of $S_1$}\big)}+3_{\text{out of $e,f$}}=18$.

* Both the vertices $e$ and $f$ have one neighbor in $S_1$.
Suppose $a$ is the common neighbor of $e$ and $f$ (see Figure <ref>(iii)).  Similarly as before, $a$ cannot have an outer edge, and $e$ and $f$ can have one outer edge each.  If the vertices $e$ and $f$ are adjacent, $e$ and $f$ have no outer edges.  If there is no edge between the vertices in $S_1$, the maximum number of edges deleted is at most $13+3_{\text{out of $S_1$}}+2_{\text{out of $e,f$}}=18$.   If $a$ and $b$ are adjacent, then $b$ does not have an outer edge.  Otherwise, we find an $S_{3,4}$ with $yb$ as the backbone.  Similarly for the other edges in $S_1$.  Hence in this case, the maximum number of edges deleted is at most $13+3_{\big(\text{in $S_1$}+\text{out of $S_1$}\big)}+2_{\text{out of $e,f$}}=18$.  Suppose $a$ is the neighbor of $e$ and $d$ is the neighbor of $f$ (see Figure <ref>(iv)). Similarly as before, $a$ and $d$ both cannot have an outer edge, and $e$ and $f$ can have one outer edge each.  If the vertices $e$ and $f$ are adjacent, then both of them have no outer edges.  If there is no edge between the vertices in $S_1$, the maximum number of edges deleted is at most $13+2_{\text{out of $S_1$}}+2_{\text{out of $e,f$}}=17$.   If $a$ and $b$ are adjacent, then $b$ does not have an outer edge.  Similarly for the other edges in $S_1$, except $ad$.  The vertices $a$ and $d$ can be adjacent without any other constraints.  Hence in this case, the maximum number of edges deleted is at most $13+3_{\big(\text{in $S_1$}+\text{out of $S_1$}\big)}+2_{\text{out of $e,f$}}=18$.

* One of the vertices $e$ or $f$ has two neighbors in $S_1$, while the other has none.  Suppose $e$ is neighbor of $a$ and $d$, while $f$ has no neighbors in $S_1$ (see Figure <ref>(v)).  The vertex $e$ does not have any outer edge.  Similarly as before, the vertices $a$ and $d$ cannot have an outer edge, whereas $f$ can have two outer edges.  If $e$ and $f$ are adjacent, then $f$ can have only one outer edge.  If there is no edge between the vertices in $S_1$, the maximum number of edges deleted is at most $13+2_{\text{out of $S_1$}}+2_{\text{out of $f$}}=17$.  If $a$ and $b$ are adjacent, then $b$ does not have an outer edge.  Similarly for the other edges in $S_1$, except $ad$.  The vertices $a$ and $d$ can be adjacent without any other constraints.  Hence, the maximum number of edges deleted is at most $13+3_{\big(\text{in $S_1$}+\text{out of $S_1$}\big)}+2_{\text{out of $f$}}=18$.

* One of the vertices $e$ or $f$ has two neighbors in $S_1$, while the other has one.
Suppose $e$ is neighbor of $a$ and $d$, while $f$ is neighbor of $d$ (see Figure <ref>(vi)).  Similarly as before, the vertices $a,d$ and $e$ cannot have an outer edge, whereas $f$ can have one outer edge.  If $e$ and $f$ are adjacent, then $f$ cannot have an one outer edge.  If there is no edge between the vertices in $S_1$, the maximum number of edges deleted is at most $14+2_{\text{out of $S_1$}}+1_{\text{out of $f$}}=17$.  In the other case, the vertices $a$ and $d$ can be adjacent without any other constraints.  If $a$ and $b$ are adjacent, then $b$ does not have an outer edge.  Similarly for the other edges in $S_1$, except $ad$.  Hence, the maximum number of edges deleted is at most $14+3_{\big(\text{in $S_1$}+\text{out of $S_1$}\big)}+1_{\text{out of $f$}}=18$.
Suppose $e$ is neighbor of $a$ and $d$, while $f$ is neighbor of $c$ (see Figure <ref>(vii)).  Similarly as before, the vertices $a,c, d$ and $e$ cannot have an outer edge, whereas $f$ can have one outer edge.  If there is no edge between the vertices in $S_1$, the maximum number of edges deleted is at most $14+1_{\text{out of $S_1$}}+1_{\text{out of $f$}}=16$.  In the other case, the vertices $a,c$ and $d$ can be adjacent without any other constraints.  Hence, the maximum number of edges deleted is at most $14+3_{\text{in $S_1$}}+1_{\text{out of $f$}}=18$.

* Both the vertices $e$ and $f$ have two neighbors in $S_1$.
Suppose $e$ is neighbor of $a$ and $d$, while $f$ is neighbor of $c$ and $d$ (see Figure <ref>(viii)).  Similarly as before, the vertices $a, c, d, e$ and $f$ cannot have an outer edge.  If there is no edge between the vertices in $S_1$, the maximum number of edges deleted is at most $15+1_{\text{out of $S_1$}}=16$.   In the other case, the vertices $a,c$ and $d$ can be adjacent without any other constraints.  Thus the maximum number of edges deleted is $15+3_{\big(\text{in $S_1$}+\text{out of $S_1$}\big)}=18$.  Suppose $e$ is neighbor of $a$ and $d$, while $f$ is neighbor of $b$ and $c$ (see Figure <ref>(ix)).  Similarly as before, the vertices $a, b, c, d, e$ and $f$ cannot have an outer edge.  The vertices $a,b,c$ and $d$ can be form a path of length $3$ without any other constraints.  In this case, the maximum number of edges deleted is $15+3_{\text{in $S_1$}}=18$.

Thus by induction
$$e(G)=e(G-H)+19\leq \frac{20}{7}(n-8)+19< \frac{20}{7}n,$$
and we are done.

If there is a $6$-$6$ edge in $G$, then $e(G)\leq \frac{20}{7}n$.

Let $xy\in E(G)$ be a $6$-$6$ edge. We subdivide the cases based on the number of triangles sitting on the edge $xy$.

* There are $5$ triangles sitting on the edge $xy$.   Let $a,b,c,d$ and $e$ be vertices in $G$ which are adjacent to both $x$ and $y$, see Figure <ref>.  Let $S_1$ denote the set of vertices $\{a,b,c,d,e\}$, and $H$ denote $S_1\cup \{x,y\}$.  We delete the vertices in the set $H$.  The vertices in $S_1$ can have one outer edge each and also form a path of length $4$ within $S_1$.  Hence the maximum number of edges deleted is $11+5_{\text{out of $S_1$}}+4_{\text{inside $S_1$}}=20$.  By the induction hypothesis, we get $e(G-H)\leq \frac{20}{7}(n-7)$. Hence, $e(G)=e(G-H)+20\leq \frac{20}{7}(n-7)+20\leq\frac{20}{7}n$.

* There are $4$ triangles sitting on the edge $xy$.  Let $a,b,c$ and $d$ be vertices in $G$ which are adjacent to both $x$ and $y$.  Let $e$ be the vertex adjacent to $x$ but not adjacent to $y$, and $f$ be adjacent to $y$ and but not adjacent to $x$.   Denote $S_1=\{a,b,c,d\}$ and $H=\{x,y\}\cup S_1\cup\{e,f\}$.  Deleting the vertices in $H$.  The vertices $e$ and $f$ can have at most two outer edge.  We differentiate the cases based on the neighbors of $e$ and $f$ as follows:

* The vertices $e$ and $f$ have no neighbors in $S_1$, see Figure <ref>(i)).
The vertices in $S_1$ can have one outer edge each and can form a path of length $3$ in $S_1$.  If the vertices $e$ and $f$ are adjacent, then both of them can have only one outer edge.  Otherwise we have an $S_{3,4}$ with $ex$ (or $fy$) as the backbone.  Hence in this case, the maximum number of edges deleted is at most $11+3_{\text{inside $S_1$}}+4_{\text{out of $S_1$}}+4_{\text{out of $e,f$}}=22$.

* One of the vertices $e$ or $f$ has one neighbor in $S_1$, while the other has none.
Assume that $e$ and $a$ are adjacent, see Figure <ref>(ii).  The vertex $a$ cannot have an outer edge and $e$ has only one outer edge.  Otherwise if $a$ has an outer edge, $ya$ is the backbone of a $S_{3,4}$.  If the vertices $e$ and $f$ are adjacent, then both of them can have only one outer edge.  Otherwise we have an $S_{3,4}$ with $ex$ (or $fy$) as the backbone.   Similarly as before, the vertices $b,c$ and $d$ can have one outer edge each and the vertices $\{a,b,c,d\}$ can form a path of length $3$ in $S_1$.  Hence in this case, the maximum number of edges deleted is at most $12+3_{\text{inside $S_1$}}+3_{\text{out of $S_1$}}+3_{\text{out of $e,f$}}=21$.

* The vertices $e$ and $f$ have one neighbor in $S_1$.
Suppose $a$ is the common neighbor of $e$ and $f$, see Figure <ref>(iii).  Similarly as before, $a$ cannot have an outer edge, and $e$ and $f$ can have one outer edge each.  The vertices $b,c$ and $d$ can  have  one  outer  edge  each  and  the  vertices $\{a,b,c,d\}$ can form  a path of length $3$ in $S_1$.  If the vertices $e$ and $f$ are adjacent, then both of them can have only one outer edge.  Hence in this case, the maximum number of edges deleted is at most $13+3_{\text{inside $S_1$}}+3_{\text{out of $S_1$}}+2_{\text{out of $e,f$}}=21$.

Suppose $a$ is the neighbor of $e$ and $d$ is the neighbor of $f$, see Figure <ref>(iv). Similarly as before, $a$ and $d$ both cannot have an outer edge, and $e$ and $f$ can have one outer edge each.  The  vertices $b$ and $c$ can  have  one  outer  edge each and  the  vertices $\{a,b,c,d\}$ can form a path of length $3$ in $S_1$.  If the vertices $e$ and $f$ are adjacent, then both of them can have only one outer edge.  Hence in this case, the maximum number of edges deleted is at most $13+3_{\text{inside $S_1$}}+2_{\text{out of $S_1$}}+2_{\text{out of $e,f$}}=20$.

* One of the vertices $e$ or $f$ has two neighbors in $S_1$, while the other has none.
Suppose $e$ is the neighbor of $a$ and $d$, see Figure <ref>(v). Similarly as before, $a$ and $d$ both cannot have an outer edge, and $e$ has one outer edge.  The vertices $b$ and $c$ can have one outer edge each and the vertices $\{a,b,c,d\}$ can form a path of length $3$ in $S_1$.  Thus the maximum number of edges deleted is at most $13+3_{\text{in $S_1$}}+2_{\text{out of $S_1$}}+3_{\text{out of $e,f$}}=21$.

* One of the vertices $e$ or $f$ has two neighbors in $S_1$, while the other has one neighbor.
Suppose $e$ is the neighbor of $a$ and $d$, and $f$ is the neighbor of $d$ (see Figure <ref>(vi)).  Similarly as before, $a$ and $d$ both cannot have an outer edge.  The vertices $e$ and $f$ can have one outer edge each.  On the other hand, the vertices  $b$ and $c$ can have one outer edge each and the vertices $\{a,b,c,d\}$ can form a path of length $3$ in $S_1$.  Thus the maximum number of edges deleted is at most $14+3_{\text{in $S_1$}}+2_{\text{out of $S_1$}}+2_{\text{out of $e,f$}}=21$.

In the other case, assume that $e$ is the neighbor of $a$ and $d$, and $f$ is the neighbor of $b$ (see Figure <ref>(vii)).  The vertices $a,b$ and $d$ cannot have an outer edge, but they along with $c$ can form a path of length $3$ in $S_1$.  The vertices $c,e$ and $f$ can have one outer edge each.  Thus the maximum number of edges deleted is at most $14+3_{\text{in $S_1$}}+1_{\text{out of $S_1$}}+2_{\text{out of $e,f$}}=20$.

* Both the vertices $e$ and $f$ have two neighbors in $S_1$.  Suppose $e$ and $f$ are neighbors of $a$ and $d$ both, see Figure <ref>(viii).  Similarly as before, $a$ and $d$ both cannot have an outer edge.  The vertices $e$ and $f$ can have one outer edge each.  The vertices $b$ and $c$ can have one outer edge each.  The vertices $\{a,b,c,d\}$ can form a path of length $3$ in $S_1$.  Thus the maximum number of edges deleted is at most $15+3_{\text{in $S_1$}}+2_{\text{out of $S_1$}}+2_{\text{out of $e,f$}}=22$.

On the other hand, assume $e$ is the neighbor of $a$ and $d$ both, while $f$ is the neighbor of $a$ and $b$ (see Figure <ref>(ix)).  The vertices $a,b$ and $d$ cannot have an outer edge, but they along with $c$ can form a path of length $3$ in $S_1$. The vertices $c,e$ and $f$ can have one outer edge each.  Thus the maximum number of edges deleted is at most $15+3_{\text{in $S_1$}}+1_{\text{out of $S_1$}}+2_{\text{out of $e,f$}}=21$.

In the last case, assume $e$ is the neighbor of $a$ and $d$ both, while $f$ is the neighbor of $b$ and $c$ (see Figure <ref>(x)).  The vertices $a,b,c$ and $d$ cannot have an outer edge, but they can form a path of length $3$ in $S_1$.  The vertices $e$ and $f$ can have one outer edge each.  Thus the maximum number of edges deleted is at most $15+3_{\text{in $S_1$}}+2_{\text{out of $e,f$}}=20$.

By the induction hypothesis, we get $e(G-H)\leq \frac{20}{7}(n-8)$. Hence, $e(G)=e(G-H)+22\leq \frac{20}{7}(n-8)+22\leq\frac{20}{7}n$.

Take $x,y\in V(G)$.  By the previous claims, if $d(x)+d(y)\geq 12$, we are done by induction.  Assume $d(x)+d(y)\leq 11$.  Summing it over all the edge pairs in $G$, we have $11e\geq \sum_{xy\in E(G)}\left(d(x)+d(y)\right)=\sum_{x\in V(G)}(d(x))^2\geq n\overline{d}^2=n(\frac{2e}{n})^2$, where $\overline{d}$ is the average degree of $G$.  This gives us $e\leq \frac{11}{4}n\leq \frac{20}{7}n$ for $n\geq1$.

§ CONCLUSIONS

Regarding the case of $\ex_{\mathcal{P}}(n,S_{2,4})$, we conjecture that the extremal construction is $\floor{\frac{n}{7}}$ disjoint copies of maximal planar graphs on $7$ vertices.  Hence,

For a given $n$, the maximum number of edges in an $S_{2,4}$ free graph on $n$ vertices is $\text{ex}_{\mathcal{P}}(n,S_{2,4})=\frac{15}{7}n$.

Concerning the exact value of $\ex_{\mathcal{P}}(n,S_{3,3})$, we conjecture the following considering the constructions for different parities of $n$.

\begin{equation*}\ex_{\p}(n,S_{3,3})=
\begin{cases}
3n-6, &\text{ if $3\leq n\leq 7$,}\\
16, &\text{if $n=8$,}\\
18, &\text{if $n=9$,}\\
\left\lfloor{\frac{5}{2}n}\right\rfloor-5, &\text{otherwise}.
\end{cases}
\end{equation*}

We have the following conjecture regarding the case of $\ex_{\mathcal{P}}(n,S_{3,4})$:

For a given $n$, the maximum number of edges in an $S_{3,4}$ free graph on $n$ vertices is $\text{ex}_{\mathcal{P}}(n,S_{3,4})=\frac{5}{2}n$.

The conjectured extremal graph is disjoint copies of $5$-regular maximal planar graphs with $12$ vertices, see Figure <ref>.

[ thick] (0,0) circle (40cm);
[fill=black](0, 40)circle(50pt);
[fill=black](0, 26)circle(50pt);
[fill=black](0, -13)circle(50pt);
[ thick](0,40)–(23,13)–(35,-20)–(0,-26)–(-35,-20)–(-23,13)–(0,40)(0,26)–(23,13)–(23,-13)–(0,-26)–(-23,-13)–(-23,13)–(0,26)(0,40)–(0,26)(35,-20)–(23,-13)(-35,-20)–(-23,-13)(0,-13)–(11,6.5)–(-11,6.5)–(0,-13)(11,6.5)–(23,13)(-11,6.5)–(-23,13)(0,-13)–(0,-26)(0,26)–(11,6.5)(0,26)–(-11,6.5)(0,-13)–(23,-13)–(11,6.5)(0,-13)–(-23,-13)–(-11,6.5);
[ thick] (0,0) circle (40cm);
[fill=black](0, 40)circle(50pt);
[fill=black](0, 26)circle(50pt);
[fill=black](0, -13)circle(50pt);
[ thick](0,40)–(23,13)–(35,-20)–(0,-26)–(-35,-20)–(-23,13)–(0,40)(0,26)–(23,13)–(23,-13)–(0,-26)–(-23,-13)–(-23,13)–(0,26)(0,40)–(0,26)(35,-20)–(23,-13)(-35,-20)–(-23,-13)(0,-13)–(11,6.5)–(-11,6.5)–(0,-13)(11,6.5)–(23,13)(-11,6.5)–(-23,13)(0,-13)–(0,-26)(0,26)–(11,6.5)(0,26)–(-11,6.5)(0,-13)–(23,-13)–(11,6.5)(0,-13)–(-23,-13)–(-11,6.5);
[ thick] (0,0) circle (40cm);
[fill=black](0, 40)circle(50pt);
[fill=black](0, 26)circle(50pt);
[fill=black](0, -13)circle(50pt);
[ thick](0,40)–(23,13)–(35,-20)–(0,-26)–(-35,-20)–(-23,13)–(0,40)(0,26)–(23,13)–(23,-13)–(0,-26)–(-23,-13)–(-23,13)–(0,26)(0,40)–(0,26)(35,-20)–(23,-13)(-35,-20)–(-23,-13)(0,-13)–(11,6.5)–(-11,6.5)–(0,-13)(11,6.5)–(23,13)(-11,6.5)–(-23,13)(0,-13)–(0,-26)(0,26)–(11,6.5)(0,26)–(-11,6.5)(0,-13)–(23,-13)–(11,6.5)(0,-13)–(-23,-13)–(-11,6.5);
[ thick] (0,0) circle (40cm);
[fill=black](0, 40)circle(50pt);
[fill=black](0, 26)circle(50pt);
[fill=black](0, -13)circle(50pt);
[ thick](0,40)–(23,13)–(35,-20)–(0,-26)–(-35,-20)–(-23,13)–(0,40)(0,26)–(23,13)–(23,-13)–(0,-26)–(-23,-13)–(-23,13)–(0,26)(0,40)–(0,26)(35,-20)–(23,-13)(-35,-20)–(-23,-13)(0,-13)–(11,6.5)–(-11,6.5)–(0,-13)(11,6.5)–(23,13)(-11,6.5)–(-23,13)(0,-13)–(0,-26)(0,26)–(11,6.5)(0,26)–(-11,6.5)(0,-13)–(23,-13)–(11,6.5)(0,-13)–(-23,-13)–(-11,6.5);

$\left(n/12\right)$-disjoint copies of $5$-regular maximal planar graphs with $12$ vertices.

We have the following conjecture for the case of $\ex_{\mathcal{P}}(n,S_{3,5})$:

For a given $n$, the maximum number of edges in an $S_{3,5}$ free graph on $n$ vertices is $\text{ex}_{\mathcal{P}}(n,S_{3,5})=\frac{8}{3}n+\Theta(1).$

We give an $n$-vertex $S_{3,5}$-free planar graph construction that justifies the lower bound.

Let $n$ be a multiple of $3$. Construct an $n$-vertex planar graph $Q_n$ using concentric $\frac{n}{3}$ cycles of length three with vertices $\{a_i, b_i,c_i\}$, $1\leq i\leq \frac{n}{3}$( where the $a_i$'s, $b_i$'s
and $c_i$'s are aligned on the same side) and joining the vertices in each set of  $A:=\{a_1,a_2,\dots,a_{\frac{n}{3}}\}$, $B:=\{b_1,b_2,\dots,b_{\frac{n}{3}}\}$  and $C:=\{c_1,c_2,\dots,c_{\frac{n}{3}}\}$ to form a path of $\frac{n}{3}$ vertices. See Figure <ref>.

[blue, fill opacity=0.2] plot coordinates(0,10)(0,30)(-26,-15)(26,-15)(8.66,-5)(-8.66,-5)(0,10);
[blue, fill opacity=0.2] plot coordinates(0,10)(0,30)(26,-15)(8.66,-5)(0,10);

[blue, fill opacity=0.2] plot coordinates(0,40)(0,60)(-52,-30)(52,-30)(34.6,-20)(-34.6,-20)(0,40);
[blue, fill opacity=0.2] plot coordinates(0,40)(0,60)(52,-30)(34.6,-20)(0,40);

[blue, fill opacity=0.2] plot coordinates(0,70)(0,90)(-78,-45)(78,-45)(60.6,-35)(-60.6,-35)(0,70);
[blue, fill opacity=0.2] plot coordinates(0,70)(0,90)(78,-45)(60.6,-35)(0,70);

[ultra thick](0,10)–(8.66,-5)–(-8.66,-5)–(0,10)(0,20)–(17.3,-10)–(-17.3,-10)–(0,20) (0,30)–(26,-15)–(-26,-15)–(0,30)(0,40)–(34.6,-20)–(-34.6,-20)–(0,40)(0,50)–(43.3,-25)–(-43.3,-25)–(0,50)(0,60)–(52,-30)–(-52,-30)–(0,60)(0,70)–(60.6,-35)–(-60.6,-35)–(0,70)(0,80)–(69.3,-40)–(-69.3,-40)–(0,80)(0,90)–(78,-45)–(-78,-45)–(0,90);
[ultra thick](0,10)–(0,60)(8.66,-5)–(52,-30)(-8.66,-5)–(-52,-30);
[ultra thick](0,70)–(0,90)(60.6,-35)–(78,-45)(-60.6,-35)–(-78,-45);
[rotate around=90:(0,50),red] (0,50) ellipse (48 and 15);
[rotate around=210:(-43.3,-25),red] (-43.3,-25) ellipse (48 and 15);
[rotate around=330:(43.3,-25),red] (43.3,-25) ellipse (48 and 15);
at (0,105) $A$;
at (-91,-52.5) $B$;
at (91,-52.5) $C$;
at (0,4) $a_1$;
at (0,94) $a_{\frac{n}{3}}$;
at (-3.4,-2) $b_1$;
at (-82,-49) $b_{\frac{n}{3}}$;
at (3.4,-2) $c_1$;
at (82,-49) $c_{\frac{n}{3}}$;

An $n$-vertex planar graph $Q_n.$

An $n$-vertex planar graph $G_n$ is constructed from $Q_n$ as follows. The vertex set of $G_n$ is $V(G_n):=V(Q_n)$. The edge set of $G_n$ is defined as $E(G_n):=E(Q_n)\cup R$. Where $R$ is defined as follows. Let $j\in \{1,2,\dots,\frac{n}{3}\}$ and $3|j$. Define the set of edges $R_j$ as

[ultra thick, red](0,30)–(-17.3,-10)(0,20)–(-8.66,-5)(-26,-15)–(17.3,-10)(-17.3,-10)–(8.66,-5)(26,-15)–(0,20)(17.3,-10)–(0,10);

[blue, fill opacity=0.2] plot coordinates(0,10)(0,30)(-26,-15)(26,-15)(8.66,-5)(-8.66,-5)(0,10);
[blue, fill opacity=0.2] plot coordinates(0,10)(0,30)(26,-15)(8.66,-5)(0,10);
[ultra thick](0,10)–(8.66,-5)–(-8.66,-5)–(0,10)(0,20)–(17.3,-10)–(-17.3,-10)–(0,20) (0,30)–(26,-15)–(-26,-15)–(0,30)(0,10)–(0,30)(-8.66,-5)–(-26,-15)(8.66,-5)–(26,-15);

at (0,4) $a_{j-2}$;
at (-3.4,-2) $b_{j-2}$;
at (3.4,-2) $c_{j-2}$;
at (0,34) $a_{j}$;
at (-29,-17) $b_{j}$;
at (29,-17) $c_{j}$;
at (4,20) $a_{j-1}$;
at (-16,-12.5) $b_{j-1}$;
at (16,-12) $c_{j-1}$;

Graph showing edges in $R_j$

See Figure <ref> to visualize the structure. Then $R$ is defined as
$$R=\bigcup_{j\in\{1,2,\dots,n/3\}, \ 3|j}R_j.$$
Figure <ref> shows the construction of $G_n$.

[blue, fill opacity=0.2] plot coordinates(0,10)(0,30)(-26,-15)(26,-15)(8.66,-5)(-8.66,-5)(0,10);
[blue, fill opacity=0.2] plot coordinates(0,10)(0,30)(26,-15)(8.66,-5)(0,10);

[blue, fill opacity=0.2] plot coordinates(0,40)(0,60)(-52,-30)(52,-30)(34.6,-20)(-34.6,-20)(0,40);
[blue, fill opacity=0.2] plot coordinates(0,40)(0,60)(52,-30)(34.6,-20)(0,40);

[blue, fill opacity=0.2] plot coordinates(0,70)(0,90)(-78,-45)(78,-45)(60.6,-35)(-60.6,-35)(0,70);
[blue, fill opacity=0.2] plot coordinates(0,70)(0,90)(78,-45)(60.6,-35)(0,70);

[ultra thick](0,10)–(8.66,-5)–(-8.66,-5)–(0,10)(0,20)–(17.3,-10)–(-17.3,-10)–(0,20) (0,30)–(26,-15)–(-26,-15)–(0,30)(0,40)–(34.6,-20)–(-34.6,-20)–(0,40)(0,50)–(43.3,-25)–(-43.3,-25)–(0,50)(0,60)–(52,-30)–(-52,-30)–(0,60)(0,70)–(60.6,-35)–(-60.6,-35)–(0,70)(0,80)–(69.3,-40)–(-69.3,-40)–(0,80)(0,90)–(78,-45)–(-78,-45)–(0,90);
[ultra thick](0,10)–(0,60)(8.66,-5)–(52,-30)(-8.66,-5)–(-52,-30);
[ultra thick](0,70)–(0,90)(60.6,-35)–(78,-45)(-60.6,-35)–(-78,-45);
[ultra thick, red](0,30)–(-17.3,-10)(0,20)–(-8.66,-5)(-26,-15)–(17.3,-10)(-17.3,-10)–(8.66,-5)(26,-15)–(0,20)(17.3,-10)–(0,10);

[ultra thick, red](0,60)–(-43.3,-25)(0,50)–(-34.6,-20)(-52,-30)–(43.3,-25)(-43.3,-25)–(34.6,-20)(52,-30)–(0,50)(43.3,-25)–(0,40);

[ultra thick, red](0,90)–(-69.3,-40)(0,80)–(-60.6,-35)(-78,-45)–(69.3,-40)(-69.3,-40)–(60.6,-35)(78,-45)–(0,80)(69.3,-40)–(0,70);

Structure of an $S_{3,5}$-free graph $G_n$.

$G_n$ is an $S_{3,5}$-free planar graph containing $\frac{8}{3}n$ edges.

$G_n$ is a planar graph clearly.

Notice that, all vertices of $G_n$ except the vertices in $\{a_1,b_1,c_1, a_{n/3},b_{n/3},c_{n/3}\}$ are of degree 5 or degree 6. Moreover, it can be checked that almost $n/3$ and $2n/3$ vertices of $G_n$ are of degree $6$ and $5$ respectively. Thus, using the fact that $2e(G)=\sum_{v\in V(G)}d(v)$ we get that $e(G_n)\approx \frac{1}{2}\left(6\dot (n/3)+5\dot(2n/3)\right)=8n/3.$

Next we show that $G_n$ does not contain $S_{3,5}.$
Observe that if there is an edge $xy$ with $d(x)=d(y)=6$ in an $S_{3,5}$-free planar graph $G$, the edge must be contained in at least $3$ triangles. From Figure <ref> it can be seen that for $j\in[n/3]$ and $3|j$, the vertices $a_{j-1}$,$b_{j-1}$ and $c_{j-1}$ are all degree $6$, where as the vertices $a_{j},b_j,c_j, a_{j-2},b_{j-2}$ and $c_{j-2}$ are all degree $5$ vertices except when $j=1$ or $j=n/3$( where in those cases the degrees are $4$). Thus in graph $G_n$ an edge whose end vertices are of degree $6$ is either $a_{j-1}b_{j-1}$ or $b_{j-1}c_{j-1}$ or $a_{j-1}c_{j-1}$ for each $j\in [n/3]$ and $3|j$. Without loss of generality take such an edge $a_{j-1}b_{j-1}$. In this case it can be seen from Figure <ref> that $d(a_{j-1},b_{j-1})=\{a_j,b_{j-2},c_{j-1}\}.$. This imply that there is no edge with end vertices of degree $6$ is contained in at most $2$ triangles.

Observe that if there is an edge $xy$ with $d(x)=5$ and $d(y)=6$ in an $S_{3,5}$-free
planar graph $G$, the edge must be contained in at least $2$ triangles. Otherwise it is easy to get find an $S_{3,5}$, which is a contradiction to the assumption. From Figure <ref> it can be seen that for $j\in[n/3]$ and $3|j$, the set of edges with end vertices 5 and 6 is $E_{1j}\cup E_{2j}\cup E_{3j}$, where $E_{1j}=\{a_jb_{j-1},b_jc_{j-1},c_ja_{j-1}\}$, $E_{2j}=\{a_ja_{j-1},b_jb_{j-1},c_jc_{j-1}\}$ and $E_{3j}=\{a_{j-1}a_{j-2},b_{j-1}b_{j-2},c_{j-1}c_{j-2}\}$. With out loss of generality take an edge $a_jb_{j-1}$ from $E_{1j}$. Clearly $d(a_j,b_{j-1})=\{a_{j-1},b_j\}$. Without loss of generality take an edge $a_ja_{j-1}$ from $E_{2j}$. Clearly, $d(a_j,a_{j-1})=\{b_{j-1},c_j\}$
Lately, without loss of generality take an edge $a_{j-1}a_{j-2}$ from $E_{3j}$. In this case, $d(a_{j-1},a_{j-2})=\{b_{j-2},c_{j-1}\}.$ So from the three results it can be seen that every edge $xy\in E(G_n)$ such that $d(x)=5$ and $d(y)=6$, the edge is contained in at least $2$ triangles.

Similar arguments can be given that each edge in $G_n$ whose end vertices are of degrees $4$ and $6$ is contained at least $1$ triangle. This implies, if $G_n$ contains an $S_{3,5}$, its backbone can not be a $4-6$ edge.

Therefore we conclude that $G_n$ contains no $S_{3,5}$ and this completes proof of Claim <ref>.

§ ACKNOWLEDGEMENTS

The research of the authors was partially supported by the National Research, Development and Innovation Office NKFIH, grants  K132696, and K126853.

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

journaltitleJ. Graph Theory
titleExtremal $C_4$-Free/$C_5$-Free Planar Graphs

journaltitlePubl. Math. Inst. Hung. Acad. Sci.
titleOn the number of complete subgraphs contained in certain graphs

journaltitleIsrael Journal of Mathematics
titleOn the structure of linear graphs

journaltitleActa Mathematica Hungarica
titleOn Maximal Paths and Circuits of Graphs

titlePlanar Turán number of the $6$-cycle

titlePlanar Turán Number of the $\Theta_6$

journaltitleGraphs Comb.
titlePlanar Turán Numbers of Short Paths

journaltitleElectron. J. Comb.
titleExtremal H-Free Planar Graphs

journaltitleDiscret. Math.
titleExtremal Theta-free planar graphs

journaltitleMatematikai és Fizikai Lapok
titleOn an extremal problem in Graph Theory

Russian Academy of Sciences, Steklov Mathematical Institute of Russian

journaltitleMatematicheskii Sbornik
titleOn some properties of linear complexes

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

journaltitleJ. Graph Theory
titleExtremal $C_4$-Free/$C_5$-Free Planar Graphs

journaltitlePubl. Math. Inst. Hung. Acad. Sci.
titleOn the number of complete subgraphs contained in certain graphs

journaltitleIsrael Journal of Mathematics
titleOn the structure of linear graphs

journaltitleActa Mathematica Hungarica
titleOn Maximal Paths and Circuits of Graphs

titlePlanar Turán number of the $6$-cycle

titlePlanar Turán Number of the $\Theta_6$

journaltitleGraphs Comb.
titlePlanar Turán Numbers of Short Paths

journaltitleElectron. J. Comb.
titleExtremal H-Free Planar Graphs

journaltitleDiscret. Math.
titleExtremal Theta-free planar graphs

journaltitleMatematikai és Fizikai Lapok
titleOn an extremal problem in Graph Theory

Russian Academy of Sciences, Steklov Mathematical Institute of Russian

journaltitleMatematicheskii Sbornik
titleOn some properties of linear complexes