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

$\endgroup$
0

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ "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? $\endgroup$
    – Daniel
    Dec 24, 2011 at 16:43
  • 1
    $\begingroup$ Put a pebble on each side of each edge, and count the total number of pebbles, two different ways. $\endgroup$ Dec 24, 2011 at 16:49
  • $\begingroup$ 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... $\endgroup$
    – N. S.
    Dec 24, 2011 at 17:21
  • $\begingroup$ Thanks for your answer, got it now! :) $\endgroup$
    – Daniel
    Dec 24, 2011 at 17:35
2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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