what is the maximum number of faces with n vertex in planar graphs?
v=number of vertices
f= number of faces
for example if v=3 -> max(f)=2
v=4 -> max(f)=4 (a triangle with a point in inner face of it , connected to the three vertex)
v=6-> max(f)=8
[Math] what is the maximum number of faces with n vertex in planar graphs
algebraic-graph-theorygraph theoryplanar-graphs
Related Solutions
The answer to all your questions is no, in general. Simple example:
Here the left picture has one $5$-cycle face and three $3$-cycle faces, while the right picture has two $3$-cyle faces and two $4$-cycle faces. Both outer faces are of different lengths.
But all is not lost. The issue with the above example is that the graph is only $2$-connected. If a planar graph is $3$-connected, then the answer to your first two questions are yes! Very roughly speaking (see Diestel's book for the gory details), when $G$ is a planar $3$-connected graph, then the cycles that are faces (facial cycles) are exactly those induced cycles whose deletion does not disconnect $G$. Since this is a purely graph-theoretical property of the cycles, it implies affirmative answers to your first two questions.
I seem to recall a result stating that you can choose any facial cycle to be the outer face, so I think the answer to your third question is always no unless all faces have the same length, but I can't find a reference, and so I might be misremembering something. In any case, you can find a counterexample pretty easily: Here are two embeddings of a $3$-connected graph, but with different lengths of the outer cycle. Note that they both have two $5$-cycle faces and five $4$-cycle faces however.
(PS sorry about the childish-ly drawn pictures.)
Hints: Let $f_i$ denote the number of faces of degree $i$. Then you have $f=f_3+f_4$ and $2e=3f_3+4f_4$ (counting edges along the boundary of each face counts each edge twice). Now play with these equations, the $2v=e$ that you know, and Euler's formula to calculate $f_3$.
For the second part, you now know the value of $f_3$. If it is the case that every vertex is contained in exactly one face of degree $3$, then argue that $v=3f_3$. You can now use the above equations to find $e$ and $f_4$.
Best Answer
Euler's formula tells you $v-e+f=2\rightarrow f=e+2-v$.
Using your variables a planar graph with $m$ edges and $n$ vertices has $m+2-n$ faces. Also see here for the maximum value for a given $n$ and unrestricted $m$.
For a given $n$ suppose we have a graph which has a face that is not a triangle. Then we can divide that face into two other faces, adding more faces. Therefore the planar graph with the most faces is made up of triangles only.since every triangle has 3 edges and every edge belongs to two triangles we get $3f=2e$ or $e=\frac{3f}{2}$. So $v-\frac{3f}{2}+f=2\rightarrow f=2v-4$