1
$\begingroup$

Let $D$ be a planar drawing of a graph such that every face is a triangle. Color the vertices of $D$ in blue, red, or green (without additional conditions). Prove that the number of faces with differently colored edges is even. Hint - count in two different ways the pairs $(F,e)$ such that $F$ is a face and $e$ is an edge of it with edges colored in red and blue.

I'm trying to understand the answer here but I don't understand why $\#\text{edges}/2=\#\text{areas}$. For instance, taking 2 squares side by side gives a graph with seven edges and three faces... Can anyone explain the idea? How can I use the fact all faces are square?

$\endgroup$

1 Answer 1

1
$\begingroup$

Each edge touches two faces and each face touches four edges. These two count the same thing (edge-face contact), so they are equal, and we get $2E = 4F$, or $\frac{E}{2} = F$.

Your example doesn't work because the outside face borders $6$ edges and is not a square.

$\endgroup$
2

You must log in to answer this question.

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