1
$\begingroup$

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$?

$\endgroup$

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
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ This is only true if the graph is finite. The hexagonal tiling of the plane is regular of degree $3$. $\endgroup$ – hardmath Mar 14 '17 at 1:30
2
$\begingroup$

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

enter image description here

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

enter image description here

$\endgroup$
  • 2
    $\begingroup$ The outer region here is bounded by 10 edges. $\endgroup$ – Henning Makholm Mar 14 '17 at 1:30
  • $\begingroup$ i think he was concern just with closed regions and not the outer region, i will try to find a counterexample, if not i will remove my answer, thanks. $\endgroup$ – Ahmad Mar 14 '17 at 1:32
  • $\begingroup$ Yes, 6 edges is for closed regions. Thank you for your example. Can you explain it by using the dual graph of G whose each degree is 6? $\endgroup$ – maki Mar 14 '17 at 1:36
  • $\begingroup$ if the statement were True and you are trying to proved it,may be that its useful to use dual graph in the proving process, but i posted a counterexample, so i don't know how to explain it using dual graph, but its very easy to construct many counter examples. $\endgroup$ – Ahmad Mar 14 '17 at 1:43
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @hardmath: Right, edited. $\endgroup$ – Henning Makholm Mar 14 '17 at 20:05

Not the answer you're looking for? Browse other questions tagged or ask your own question.