# Questions of the form “let $G$ be a planar graph such that every face is a…$” Prove that… 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... ## 1 Answer 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 :-)