# Number of pentagons in a Planar graph

I have the following problem that I don't have a clue even how to start, reaching dead ends all the time.

The problem: G=(V,E) is a Planar graph, each face in this graph is hexagon or pentagon. Also, each vertex degree is 3 (deg(v) = 3). I need to prove that on each graph that follows these rules, the number of pentagons is constant and won't be changed.

Any help would be welcomed :)

EDIT: |V| = n

2|E| = 3*|V|=3n --> |E| = 3n\2

Euler's formula:

V+F-E=2

n+F-3n\2=2

-n\3+F=2

I don't have any information about the number of faces I have so I'm reaching dead end here

-

Here are the tools you need:

Euler's formula, vertices minus edges plus faces equals 2.

The degrees of the vertices add up to twice the number of edges.

Five times the number of pentagons plus six times the number of hexagons equals twice the number of edges.

That should do it.

-
"Five times the number of pentagons plus six times the number of hexagons equals twice the number of edges. " Can you please explain this? Why 5 pentagons and 6 hexagons? –  Daniel Dec 24 '11 at 16:43
Put a pebble on each side of each edge, and count the total number of pebbles, two different ways. –  Gerry Myerson Dec 24 '11 at 16:49
Basically Gerry is counting the edges by face. Each pentagon has 5 edges, each hexagon has 6 edges and each edge is counted exactly twice... This is the same trick used to prove that $K_{33}$ and $K_5$ are not planar... –  N. S. Dec 24 '11 at 17:21
Thanks for your answer, got it now! :) –  Daniel Dec 24 '11 at 17:35

Try using Euler's polyhedral formula: Vertices + Faces - Edges = 2 for planar connected graphs, as well as the other information you have. These graphs are often referred to as fullerenes.

-