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$

1 Answer 1

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$

You must log in to answer this question.

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