graph theoryplanar-graphs
Let G be a simple connected planar graph with at least three vertices. Prove
that if every face of G has degree 3, then G has an even number of faces
I've looked around and haven't found any questions similar to this.
I'm trying to prove this. I know that every face shares two edges so if I were to use Euler's formula 3f = 2m. Im not really sure where to go from there.
Let $G$ be a cubic planar graph with one hexagonal face and four square faces. By Euler's formula $$V-E+F=2,$$ where $F=7$ and $E=\tfrac32V$, and hence $V=10$. Let $G_1$ and $G_2$ be the induced subgraphs on the vertices of the hexagonal face, and on the remaining $4$ vertices respectively. Without loss of generality $G_2$ lies inside the hexagon $G_1$. Because $G$ is cubic there are precisely $6$ edges going out from $G_1$, hence going into $G_2$. It follows that there are precisely $3$ edges in $G_2$. As $G$ does not contain triangular faces $G_2$ is either a claw or a path.
If $G_2$ is a claw then each of the three leaves is adjacent to two vertices in $G_1$. Then removing the root of the claw from $G$ we can smooth out the remaining three leaves of $G_2$ to get a new planar graph on the vertices of $G_1$. Because $G$ is triangle-free this smoothing out produces three distinct edges that are not edges of $G_1$. But there is no such planar graph, a contradiction.
If $G_2$ is a path then contracting the edges adjacent to the terminal vertices yields two vertices that are each adjacent to three distinct vertices of $G_1$. As this graph is planar, it is the following graph:
Because $G$ is triangle-free the two terminal vertices of $G_2$ are adjacent to non-adjacent vertices in $G_1$, i.e. to the vertices on the left and right in the picture. Then the two middle vertices of $G_2$ are adjacent to the top and bottom vertices of $G_1$ in the picture. This is impossible as $G$ is planar.
Ths shows that there is no cubic planar graph with one hexagonal face and four square faces.
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
What's $m$? What does Euler's formula have to do with it? In fact, being planar is largely irrelevant: the same is true on surfaces of arbitrary genus.
If every face has degree $3$, every face has $3$ edges; but every edge has two faces, so $E = \frac{3}{2}F$ where $E$ is the number of edges and $F$ is the number of faces; then $2E = 3F$ and by the fundamental theorem of arithmetic $2$ must be a factor either of $3$ (which it isn't) or of $F$.