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.

  • $\begingroup$ You should use Euler formula, and the fact that $3f$ gives you twice the number of edges because each edge is counted twice. From there, you simply need to argue that the number of vertices is an integer. $\endgroup$ – Fabio Somenzi May 22 '18 at 8:27
  • $\begingroup$ So would it be something like since 3f = 2m, m = 3/2f so f has to be even? $\endgroup$ – Akshay Kumar May 22 '18 at 8:32
  • $\begingroup$ Exactly. Otherwise, plugging that value for $m$ in Euler's formula, you find that $n-2$ is not an integer. $\endgroup$ – Fabio Somenzi May 22 '18 at 8:34
  • $\begingroup$ I get what your saying, does this mean that n - 3/2f + f = 2. which only true for even faces $\endgroup$ – Akshay Kumar May 22 '18 at 8:36
  • $\begingroup$ Yes, that's the proof. $\endgroup$ – Fabio Somenzi May 22 '18 at 12:41

I know that every face shares two edges so if I were to use Euler's formula $3f = 2m$

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.