A graph $G$ is a simply connected planar graph, all of whose regions are bounded by $6$ edges. How do you prove the degree of vertex in $G$ is most $2$?
closed as off-topic by Matthew Conroy, Scientifica, Claude Leibovici, user91500, Shailesh Mar 14 '17 at 11:54
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Matthew Conroy, Scientifica, Claude Leibovici, user91500, Shailesh
Well, its not true at all,
consider this planar graph $G$ which every region in it is bounded by $6$ edges yet there is two vertices with degree $3$.
hope you see what you are looking for.
note : responding to a graph $G$ that also the outer open region is bounded by 6 edges
What you can prove is:
If $G$ is a finite, simple, connected plane graph, and all of whose regions are bounded by $6$ edges, then it has at least one vertex with degree $\le 2$.
This follows from Euler's polyhedral formula: $$ V+F = 2+E $$ When all faces are hexagonal, we have $E=3F$ and therefore $$ V = 2+2F $$ On the other hand the sum of the degrees is $2E=6F$, which is not enough to give each of the $2+2F$ vertices degree $3$ or more.