3
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Doesn't that restriction imply $n=4F_4$? $\endgroup$
    – Gerry Myerson
    Jul 20, 2014 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, 2014 at 2:16
  • 1
    $\begingroup$ Isn't there a 4-to-1 correspondence between vertices and faces of degree 4? $\endgroup$
    – Gerry Myerson
    Jul 20, 2014 at 3:32

2 Answers 2

Reset to default
3
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ Since $E/6=n/4$, this comes to the same thing as the formula in my comment on the question. $\endgroup$
    – Gerry Myerson
    Jul 21, 2014 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$
    – Studentmath
    Jul 21, 2014 at 6:51
  • $\begingroup$ @Studentmath How do we know the vertex is incident to only one face of degree 4? $\endgroup$
    – Bob
    Nov 23, 2015 at 18:16
  • $\begingroup$ @Bob It's a given fact in the question. $\endgroup$
    – Studentmath
    Nov 23, 2015 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, 2015 at 23:07
0
$\begingroup$

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?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .