Suppose G is a connected planar simple graph with $e$ edges and $v$ vertices with no cycles of length 4 or less...

Question

Suppose G is a connected planar simple graph with $e$ edges and $v$ vertices with no cycles of length 4 or less.

Prove that (For $ v ≥ 4$): $$e ≤ {\frac{5}{3}}v - {\frac{10}{3}}$$

-I have a basic understanding of planar graphs based off of our lecture in class. I understand that planar means it can be drawn on a single plane without any edges crossing and I know that since it's a connected graph it has one component, and I know that since it is a simple graph it does not contain loops or multi-edges. Although I don't understand how to tie this in with a proof such as this, any help is appreciated.

Answer 1

The following theorem is well known in graph theory (see theorem 6.10 in http://compalg.inf.elte.hu/~tony/Oktatas/TDK/FINAL/Chap%206.PDF):

For a connected simple planar graph with $v$ vertices and $e$ edges, and girth $g$, we have $$e\leq \frac{g}{g-2}(v-2)$$

Note the girth $g$ is the length of the smallest cycle.

In our case $g=5$, thus $$e\leq \frac{5}{3}(v-2)$$

Answer 2

The sum of the degree of the regions in the graph will be $2e$ as each edge contributes to 2 regions. But again, we have no circuits of length $4$ or less. So each region has degree $\geq 5$. So, $2e \geq 5f \implies \frac{2}{5}e \geq f$.

Now, apply the Euler's formula which states $v-e+f=2\implies e-v+2=f \implies e-v+2 \leq \frac{2}{5}e \implies e \leq \frac{5}{3}v - \frac{10}{3}$.

Answer 3

Maybe you are stuck at why $5$ and $g$ in the other 2 answers by tomriddle99 and M.Badaoui. Here I show the reasons behind that.

---

For any edge, it contributes 1 (in one cycle) or 2 (not in one cycle) to the degree of the region it is inside.

Then when $v=4$, it may be $C_4$ (cycle-4) which has degree 4, $C_3$ with one edge with degree 5, $C_2$ with 2 edges (but $C_2$ is excluded by not allowing the multi-edge), $C_1$ with 3 edges (excluded by not allowing the loop) or $C_0$ with 4 edges with degree 8.

For $v=1\sim 3$, the above process can also be applied although you stated $v\ge 4$.

Since "no cycles of length 4 or less", so we can only $v=5$ which has the least degree 5 when $C_5$. This is what the reference chapter by M.Badaoui says:

As g is the length of the smallest cycle in G, therefore g is the smallest degree of a region.