Maximum number of edges in a planar graph without $3$- or $4$-cycles

1.1k Views Asked by At

What is the largest possible number of edges in a planar graph without $3$- or $4$-cycles?

I've been unsuccessfully trying to solve this problem from my book. I know that every planar graph without $3$-cycles has at most $2n - 4$ edges, though I'm not sure about graphs without $4$-cycles.

1

There are 1 best solutions below

0
On

If a planar graph $G$ contains no $3$- or $4$-cycles, then given a planar embedding of $G$, every face is bounded by at least $5$ edges. Then since every edges is incident to exactly two faces, we have $5f \leq 2e$. Combining this with Euler's characteristic formula,

$$\begin{align} f-e+n = 2 &\implies 5f-5e+5n = 10 \\ &\implies 2e-5e+5n \geq 10 \\ &\implies 5n-10 \geq 3e \\\\ &\implies e \leq \left\lfloor\frac{5n-10}{3}\right\rfloor \end{align}$$