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$
3
  • $\begingroup$ What are $\alpha_i(G)$ for $i=0,1,2$? $\endgroup$ Commented Oct 31, 2015 at 15:33
  • $\begingroup$ @StefanGyürki Sorry, I forgot to specified. I made an edit, check it out. $\endgroup$
    – user72151
    Commented Oct 31, 2015 at 15:36
  • $\begingroup$ Thanks, in that case I have a solution. Wait a few minutes. $\endgroup$ Commented Oct 31, 2015 at 15:46

1 Answer 1

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
  • 2
    $\begingroup$ @Surb Thanks for the picture, I was also just about to adding it. And Stefan, thanks for the answer. $\endgroup$
    – user72151
    Commented Oct 31, 2015 at 17:21
  • $\begingroup$ Two quick questions, $\endgroup$
    – user72151
    Commented Nov 2, 2015 at 21:57

You must log in to answer this question.