1
$\begingroup$

In a connected planar graph, every vertex has degree $3$, and every face is bordered by $5$ or $6$ edges. How many faces are bordered by $5$ edges?

$\endgroup$
2
$\begingroup$

Let $n, e, f, x$ represent the number of vertices, the number of edges, the number of faces, and the number of faces bordered by $5$ edges, respectively. By the handshaking lemma, we have: $$ 2e = \sum_{v \in V} \deg v = 3n $$ Likewise, by applying the handshaking lemma to the dual graph $G^*$, we have: $$ 2e = \sum_{i} |F_i| = 5x + 6(f - x) = 6f - x \iff 6f = 2e + x $$ We can use these two equations with Euler's Formula to solve for $x$: \begin{align*} n - e + f &= 2 \\ 2(3n) - 6e + (6f) &= 12 \\ 2(2e) - 6e + (2e + x) &= 12 \\ x &= 12 \end{align*}

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