Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
"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
1  
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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