3
$\begingroup$

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

2 Answers 2

5

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.

  • 0
    Thanks for your answer, got it now! :)2011-12-24
2

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.