$G$ conex planar graph, the total number of faces

50 Views Asked by At

Let $G$ be a conex planar graph with n more or equal than $3$ vertices, so that each face will contain in its frontier a circuit of length at least $5$.So, the number of faces will be at most $(2n-4)$$/$$3$. Can someone pleae help me with this problem?

2

There are 2 best solutions below

0
On

From the given, $5f\le 2e$. Use $n+f=e+2$ to eliminate $k$.

0
On

Lemma: If $G$ is a planar graph with $V$ vertices, $E$ edges, and finite girth $g$ then, $$E \leq \frac{g(V−2)}{V−2}$$

Look here: girth in planar graph


So $g=5$ and thus $3E\leq 4V-10$. Using Euler theorem: $$V-E+F =2$$ we have $$3V+3F -6 \leq 4V-10$$ so $$F\leq {V-4\over 3}$$

which is much better bound.