Questions of the form "let $G$ be a planar graph such that every face is a...$" Prove that...

Question

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

Answer 1

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