- 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.
- 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
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
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 :-)