1
$\begingroup$

In a certain planar embedding of a 3-regular connected graph $G$, the faces have degrees either $5$ or $6$. If there are $20$ faces of degree $6$ in the embedding, how many faces of degree $5$ are there?

I was planning on using the Handshaking Lemma for Faces equation but ran into the problem that I don't know how many edges there are in this graph.

Is Euler's Equation applicable in this situation even though we don't know how many vertices or edges there are?

$\endgroup$
3
$\begingroup$

Let $e$ be the number of edges, $v$ the number of vertices and $f$ the number of degree-$5$ faces. Then

  • by the handshaking lemma for vertices, $3v=2e$;
  • by the handshaking lemma for faces, $2e=120+5f$;
  • by Euler's formula, $(20+f)+v=e+2$.

Now solve.

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