# Planar graph and isomorhic graph

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$

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

## 1 Answer

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