2
$\begingroup$

I've been given the following problem as homework:

A graph is drawn in the plane and has 78 faces, all of them triangles.  Prove the outer face is not a 19-gon. 

We're also given a hint to use the formula: |V| - |E| + |F| = 2 (for planar, connected graph, where |F| = the number of faces).

What I've tried so far: I realize the number of faces is 78, so I can plug "78" in for |F|. I realize there's probably a way to calculate |E| given that the outer face is a 19-gon, but I can't figure this out. Further, I imagine if I calculate |E|, I'll find that it doesn't satisfy this equation which proves the outer face can't be a 19-gon.

This is homework, so I'm not looking for an answer or proof. Could you give some useful hints to point me in the right direction?

  • 2
    "Proof: 3 ≠ 19."2012-05-17

1 Answers 1

1

(I'll assume "all the faces" means "all the bounded faces".)

Suppose the outer face actually is a 19-gon. How many new edges would you need to add to the outer face to cut it up into triangles? How many faces would that planar graph have?