1
$\begingroup$

Let $G = (V, E)$ be a simple, connected graph where each vertex has degree $3$. Furthermore, assume that $G$ is planar and that every vertex lies on the boundary of exactly three faces, one having a boundary consisting of $6$ edges, the other two one of $4$ edges each. Determine $\alpha_0(G)$, $\alpha_1(G)$, $\alpha_2(G)$ and draw a plane graph which is isomorphic to G.

I though of the $K_{3,3}$ graph, where each vertex has degree of $3$, but of course it's not planar. Any ideas for the above problem and graphs?

EDIT:

$\alpha_0(G)$ = |V| = number of vertices of $G$

$\alpha_1(G)$ = |E| = number of edges of $G$

$\alpha_2(G)$ = |F| = number of faces of $G$

$\endgroup$
  • $\begingroup$ What are $\alpha_i(G)$ for $i=0,1,2$? $\endgroup$ – Stefan Gyürki Oct 31 '15 at 15:33
  • $\begingroup$ @StefanGyürki Sorry, I forgot to specified. I made an edit, check it out. $\endgroup$ – user72151 Oct 31 '15 at 15:36
  • $\begingroup$ Thanks, in that case I have a solution. Wait a few minutes. $\endgroup$ – Stefan Gyürki Oct 31 '15 at 15:46
1
$\begingroup$

For a planar graph the Euler formula says: $f+n=e+2$, where $f=|F|$, $n=|V|$, $e=|E|$. Since your graph is cubic, clearly $e=3n/2$. We have that each vertex lies on a boundary of exactly one 6-cycle, therefore for the number of hexagons $b$, we have $b=n/6$. Each vertex lies on a boundary of precisely two 4-cycles, thus the number of 4-cycles $a$ is $a=2n/4=n/2$. On one hand $f=a+b=n/2+n/6=2n/3$, on the other hand $f=e+2-n=2+ n/2$. Thus $n=12$, and there are two 6-cycles and six 4-cycles in the graph. If you would like to depict your graph, then take two hexagons with vertices $v_1,v_2,\ldots,v_6$ and $w_1,\ldots,w_6$ (draw them concentrically), and join $v_i$ with $w_i$ for $i=1,2,\ldots,6$.

enter image description here

$\endgroup$
  • 2
    $\begingroup$ @Surb Thanks for the picture, I was also just about to adding it. And Stefan, thanks for the answer. $\endgroup$ – user72151 Oct 31 '15 at 17:21
  • $\begingroup$ Two quick questions, $\endgroup$ – user72151 Nov 2 '15 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy