Highest possible number of edges in a planar graph, which does not contain C3 or C4

Question

Determine the highest possible number of edges in a planar graph, which does not contain C3 or C4 (C = cycle, 3,4 = length of the cycle).

Details: you are given $n$ vertices and they are asking you the highest possible number of edges in a planar graph with the $n$ vertices, while satisfying the condition of not containing $C_3$ or $C_4$. Sorry if I was unclear, english is not my main language.

Answer 1

I will assume we are talking about simple graphs, i.e

• there are no edge that join a vertex with itself.
• between any two vertices, there is at most one edge joining them.

Otherwise, it is trivial to construct graph with $n$ vertices and arbitrary large number of edges.

Let $e$ be the number of edges of the graph.

Since the graph is planar, we can put in on the surface of a sphere. We start to remove dangling vertices, i.e vertices which connect to either $0$ or $1$ edge, from the graph. At the end, there are two possibilities:

Case I - the graph reduces to a single dangling vertex.

The original graph is a forest of trees and isolated vertices. The total number of edges $e$ is at most $n-1$.

Case II - the graph reduces to one composed of closed loops.

Let $V, E, F$ and $C$ be the number of vertices, edges, faces (on sphere) and connected components of remaining graph. It is clear $C \ge 1$, $V \ge 3C$ and we have removed $e-E \le n-V$ edges from the original graph. Let $F_k$ be the number of faces with $k$ sides. We have

• $F_1 = F_2 = 0$ because the graph is simple.
• $F_3 = F_4 = 0$ because we assume the graph doesn't contain $C_3$ nor $C_4$ as a subgraph.

This leads to $$2E = \sum_{k=5}^\infty k F_k \ge 5 \sum_{k=5}^\infty F_k = 5F$$

Since $V - E + F = 1+C$, we find: $$V - (1+C) = E - F \ge \frac32 F \quad\implies\quad F \le \frac23 (V-(1+C))$$ As a result, $$E = V + F - (1+C) \le \frac53 (V-(1+C)) \le \frac53 (V-2)$$

Adding back the $e - E$ edges we have removed before, we get:

$$e = (e-E) + E \le (n-V) + \frac53 (V-2) \le \frac53(n-2)$$

Combining estimates of these two cases, we can conclude

$$e \le \mathcal{N}(n) \stackrel{def}{=} \max\left(n-1, \left\lfloor\frac53(n-2)\right\rfloor \right) = \begin{cases} n - 1, & n \le 4,\\ \left\lfloor\frac53(n-2)\right\rfloor, & n > 5 \end{cases} $$

It turns out this upper bound $\mathcal{N}$ is optimal.

• For $n = 1,\ldots, 4$, the result is obvious.
• For $n = 5$ and $6$, the pentagon and hexagon has $\mathcal{N}(n) = n$ edges and fit the requirement.
• For $n = 7$, start from a hexagon, add one vertex and two edges inside to split the hexagon to obtain a graph of two pentagons with $\mathcal{N}(7) = 8$ edges ( left figure at picture below ).

$\hspace1.5in$

• For $n = 5+3k$ or $7+3k$ where $k > 0$, we can use the fact start from a pentagon, we can add three vertices and five edges inside to split it into $3$ pentagons (right figure at picture above). This allow one to reduce the case from $n$ to $n-3$ vertices.

• For $n = 6+3k$ where $k > 0$, we can start from the graph for $5+3k$ constructed above, split one edge by adding a vertex.