# 3-regular connected planar graph

Let $G$ be a 3-regular connected planar graph with a planar embedding where each face has degree either 4 or 6 and each vertex is incident with exactly one face of degree 4. Determine the number of vertices, edges and faces of degree 4 and 6.

Using handshake lemmas and Euler Formula, I've come up with the following for $E$ edges and $n$ vertices:

$2E=3n$

$2E=4F_4+6F_6$

$n-E+F_4+F_6=2$

I'm missing an equation because I'm not sure how to use the restriction where each vertex is incident with one face of degree 4. Any help?

• Doesn't that restriction imply $n=4F_4$? Jul 20 '14 at 2:07
• @GerryMyerson If each vertex is incident to only one face of degree 4, how does $n=4F_4$? Jul 20 '14 at 2:16
• Isn't there a 4-to-1 correspondence between vertices and faces of degree 4? Jul 20 '14 at 3:32

Consider the edges adjacent to any vertex $v\in V(G)$. We know the vertex is incident to only one face of degree 4, thus 2 of the three edges adjacent to it form part of the length of a face of degree 4. Thus, two thirds of all edges lie on the border of a face of length 4, and we have:

$f_4=\frac{1}{4}*\frac{2}{3} *e=\frac{1}{6}e$

Using this fact and the rest of your equations, you should be able to get all the values you need.

• Since $E/6=n/4$, this comes to the same thing as the formula in my comment on the question. Jul 21 '14 at 6:42
• @Gerry Correct, counting vertex-face incidences is another way to reach that. I find it easier to thinking about it edges' wise, but it's just me. Jul 21 '14 at 6:51
• @Studentmath How do we know the vertex is incident to only one face of degree 4?
– Bob
Nov 23 '15 at 18:16
• @Bob It's a given fact in the question. Nov 23 '15 at 19:39
• @Studentmath ohh my bad. Would this proof still apply if that fact was not given? Can that fact be derived?
– Bob
Nov 23 '15 at 23:07

Maybe that's just a comment, but it's too long:

You can calculate the $F_4=6$. Use $$F = F_4+F_6$$ $$2E = 3V = 4F_4+6F_6$$

Since each face contributes its edges twice; by Euler's formula $V-E+F=2$ we have:

$$6V-6E+6F = 12\\ 4E-6E+6F = 12\\ 6F-2E = 12\\ 6( F_4+F_6)-(4F_4+6F_6)=12\\ 2F_4+0F_6 = 12\\ F_4=6$$

If such a graph could be drawn I think it would answer a question of mine:

How many vertices do you need so that all squares are not directly connected?