Highest possible number of edges in a planar graph, which does not contain C3 or C4 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.
 A: 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.
