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:




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?

  • $\begingroup$ Doesn't that restriction imply $n=4F_4$? $\endgroup$ Jul 20 '14 at 2:07
  • $\begingroup$ @GerryMyerson If each vertex is incident to only one face of degree 4, how does $n=4F_4$? $\endgroup$
    – user151948
    Jul 20 '14 at 2:16
  • 1
    $\begingroup$ Isn't there a 4-to-1 correspondence between vertices and faces of degree 4? $\endgroup$ 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.

  • 1
    $\begingroup$ Since $E/6=n/4$, this comes to the same thing as the formula in my comment on the question. $\endgroup$ Jul 21 '14 at 6:42
  • $\begingroup$ @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. $\endgroup$ Jul 21 '14 at 6:51
  • $\begingroup$ @Studentmath How do we know the vertex is incident to only one face of degree 4? $\endgroup$
    – Bob
    Nov 23 '15 at 18:16
  • $\begingroup$ @Bob It's a given fact in the question. $\endgroup$ Nov 23 '15 at 19:39
  • 1
    $\begingroup$ @Studentmath ohh my bad. Would this proof still apply if that fact was not given? Can that fact be derived? $\endgroup$
    – 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?


Your Answer

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

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