1. Let $G$ be a planar graph with degrees all at least three. Suppose we can draw $G$ in a plane such that every face is a square. Prove the number of vertices of degree three is greater than the number of vertices with degree at least five.
  2. 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 the number of faces with differently colored edges is even. Hint - count in two different way 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 have no clue how to really approach this kind of problem.

The tools I have in mind are: Euler's formula, the inequality $3|F|<2|E|$ which is strict for triangulations, and the fact the average degree in a planar graph is strictly less than five. These look like powerful tools, but I don't know how to even think of a solution...


Here my hints (you saw the first one in my comment).

For the first part consider, that every area has exactly 4 edges (since it is square). Hence you get #edges/2=#areas. Now plug this into eulers formula (#vertices+#areas-#edges=2), to get some equation

2 $\times$ #points=#edges+4>#edges

On the other hand if at least half of the vertices have degree >5 the "average" vertice gives has more than degree (3+5)/2=4, hence you get the inequality

2 $\times$ #vertices < edges

which is a contradiction to above

To the second part: Use the hint and count the $(F,e)$. First way: $$\#(F,e)= \sum_{e \text{ has vertices red & blue}} 2$$ since every such edge has two such faces.

Second way: $$\#(F,e)= \sum_{F} \#e(F)$$ where $\#e(F)$ notates the number of appropriate edges. Mark, that $\#e(F)$ is 1, if $F$ has 3 different colored vertices, 2 if $F$ has no green vertice and 0 if $F$ has no blue or no red vertices.

Ending the proof: Consider in the first way, that the sum is even. Now do it :-)


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.