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?
2026-03-29 16:49:43.1774802983
On
$G$ conex planar graph, the total number of faces
50 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
2
There are 2 best solutions below
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.
From the given, $5f\le 2e$. Use $n+f=e+2$ to eliminate $k$.