1
$\begingroup$

I'm new here and I'm having difficulty with this graph theory question.

Suppose $G$ is a connected $3$-regular planar graph which has a planar embedding such that every face has degree either $5$ or $6$. I need to prove that $G$ has precisely $12$ faces of degree $5$.

I know that a $3$-regular graph is a graph where all the vertices are of degree $3$ and that a planar embedding is a graph that has no edges crossing.

  • 0
    This very interesting class of graphs is known as the fullerenes. You can find out more about them here: http://en.wikipedia.org/wiki/Fullerene2012-11-17

2 Answers 2

1

Hint: Let $G(V,\ E)$ satisfy $|V| = n$ and $|E| = m$. Then from Euler's formula we have $n - m + f = 2$ Let $f_5$ and $f_6$ denote the number of degree $5$ and $6$ faces respectively. Now apply the Handshaking lemma to relate both the number of vertices and the faces of each degree to the number of edges. Substitute the resulting relations into Euler's formula and see what you get.

1

The Euler identity for polyhedron:

$V-E+F=2$

can be transformed into this (see the details below):

$F_5+0F_6=12+F_7+2F_8+3F_9+\cdots$

and for graphs with all faces with degree 5 or 6, it becomes:

$F_5+0F_6=12$

If you check the equilibrium of the identify, since $F_6$ face do not influence the equilibrium, a graph is forced to have 12 pentagonal faces and an indefinite number of $F_6$ faces.

As answered by Joseph Malkevitch, fullerenes have these characteristics.


Details:

$F = F_2+F_3+F_4+\cdots$ $2E = 3V = 2F_2+3F_3+4F_4+\cdots$

Since a region bounded by n edges has n vertices and each vertex belongs to three regions, by Euler's formula $V-E+F=2$ we have:

$6V-6E+6F = 12$ $4E-6E+6F = 12$ $6F-2E = 12$ $6(F_2+F_3+F_4+\cdots)-(2F_2+3F_3+4F_4+\cdots) = 12$ $4F_2+3F_3+2F_4+F_5+0F_6-F_7-2F_8-3F_9-\cdots = 12$

That becomes:

$F_5+0F_6=12+F_7+2F_8+3F_9+\cdots$