0
$\begingroup$

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.

$\endgroup$
5
  • $\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, 2018 at 8:27
  • $\begingroup$ So would it be something like since 3f = 2m, m = 3/2f so f has to be even? $\endgroup$
    – tom knight
    May 22, 2018 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, 2018 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$
    – tom knight
    May 22, 2018 at 8:36
  • $\begingroup$ Yes, that's the proof. $\endgroup$
    – Fabio Somenzi
    May 22, 2018 at 12:41

1 Answer 1

Reset to default
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .