Why is the number of edges of a $C_5$-free planar graph with $n$ vertices at most $\frac{12n-33}{5}$ where $n\in\{11,12,13\}$

Question

Let us say that a graph is $C_5$-free if it does not contain any cycle $C_5$ as a subgraph (whether induced or not). We define $ex_{_\mathcal{P}}(n,C_5)$ to be the maximum number of edges possible in a $C_5$-free planar graph on $n$ vertices.

Literature [1] proves the following theorem.

Theorem 3 ([1]). $ex_{_\mathcal{P}}(n,C_5)\le \frac{12n-33}{5}$ for all $n\ge 11$.

The proof of the theorem uses induction. But the author claims that:

It can be checked systematically that the result $ex_{_\mathcal{P}}(n,C_{5}) \leq \frac{12n-33}{5}$ holds for $n \in \{11,12,13\}$ (this turns out to be
not as onerous as it might at first appear!)

I'm curious as to how the author checked systematically. Using a computer to check them one by one? It seems that the number of $C_5$-free planar graphs of order $11$ (or even more) would not be small.

• [1] Dowden C. Extremal C4‐Free/C5‐Free Planar Graphs[J]. Journal of Graph Theory, 2016, 83(3): 213-230. https://doi.org/10.1002/jgt.21991

Is there a non-computer proof? Or is computer verification really possible (as the number of planar graphs with $13$ vertices is so large)?

Answer 1

The proof of Theorem 3 is long, but only Part I uses the induction hypothesis and the assumption that there are at least $11$ vertices. In the rest of the proof, we only need to know that there are more than $4$ vertices (to exclude $K_4$) and that there are at least $7$ vertices (so that a bound of $2n-4$ implies the bound we want).

In particular, for $n=7, 8, \dots, 13$, the only potential way to violate the theorem is if the graph $G$ has $\delta(G) \le 2$ or $\kappa(G) \le 1$.

Let's do the following brute-force searches (each of which is considerably less intense because there are fewer than $1000$ graphs to consider in each case):

• When $n \le 4$, $K_n$ is a $C_5$-free planar graph with $\binom n2$ edges. (Trivially but importantly, this is unique.)
• When $n=5$, the $C_5$-free planar graph with the most edges has $7$ edges: one option is $K_{1,1,3}$.
• When $n=6$, the $C_5$-free planar graph with the most edges has $9$ edges: one option is $K_{1,1,4}$.
• When $n=7$, the $C_5$-free planar graph with the most edges has $12$ edges: it is two copies of $K_4$ joined at a vertex. Importantly, it is unique.

From here on, we apply the non-Part-I version of the theorem, but also consider the cases where $\delta(G)\le2$ or $\kappa(G)\le1$.

• When $n=8$, the bound $\frac{12n-33}{5}$ gives us $12$ edges. Or, we could have a vertex of degree $2$ or less, in which case we have at most $12+2 = 14$ edges. However, there is no way to add a degree-$2$ vertex to the extremal $7$-vertex graph without creating a $5$-cycle, so we actually get at most $13$ this way. Or, we could have a cut vertex, in which case we have at most $\max\{12+1,9+3,7+6\} = 13$ edges. Altogether, our bound is $13$.
• When $n=9$, the bound $\frac{12n-33}{5}$ gives us $15$ edges. Or, we could have a vertex of degree $2$ or less, in which case we have at most $13+2 = 15$ edges. Or, we could have a cut vertex, in which case we have at most $\max\{13+1,12+3,9+6,7+7\} = 15$ edges. Altogether, our bound is $15$.
• When $n=10$, the bound $\frac{12n-33}{5}$ gives us $17$ edges. Or, we could have a vertex of degree $2$ or less, in which case we have at most $15+2 = 12$ edges. Or, we could have a cut vertex, in which case we have at most $\max\{15+1,13+3,12+6,9+7\} = 18$ edges. Altogether, our bound is $18$. Moreover, the $18$-edge example is unique, since the $12$-edge and $6$-edge pieces we joined along a cut vertex are unique: it must be three copies of $K_4$ joined at a cut vertex.
• When $n=11$, the bound $\frac{12n-33}{5}$ gives us $19$ edges. Or, we could have a vertex of degree $2$ or less, in which case we have at most $18+2 = 20$ edges. However, there is no way to add a degree-$2$ vertex to the extremal $10$-vertex graph without creating a $5$-cycle, so we actually get at most $19$ this way. Or, we could have a cut vertex, in which case we have at most $\max\{18+1,15+3,13+6,12+7, 9+9\} = 19$ edges. Altogether, our bound is $19$.
• When $n=12$, the bound $\frac{12n-33}{5}$ gives us $22$ edges. Or, we could have a vertex of degree $2$ or less, in which case we have at most $19+2 = 21$ edges. Or, we could have a cut vertex, in which case we have at most $\max\{19+1,18+3,15+6,13+7,12+9\} = 21$ edges. Altogether, our bound is $22$.
• When $n=13$, the bound $\frac{12n-33}{5}$ gives us $24$ edges. Or, we could have a vertex of degree $2$ or less, in which case we have at most $22+2 = 24$ edges. Or, we could have a cut vertex, in which case we have at most $\max\{22+1,19+3,18+6,15+7,13+9,12+12\} = 24$ edges. Altogether, our bound is $24$.

We see that for $11 \le n \le 13$, we don't get better bounds from graphs with $\delta(G)\le2$ or $\kappa(G)\le1$ than we do for other graphs (for which the theorem is already known to hold). Therefore the theorem holds when $11 \le n \le 13$.