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.

$\endgroup$
4
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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