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$
1
  • 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, 2017 at 1:30

2 Answers 2

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$
4
  • 2
    $\begingroup$ The outer region here is bounded by 10 edges. $\endgroup$ Mar 14, 2017 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, 2017 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, 2017 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, 2017 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$
1

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