Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The problem is this:

Let $G$ be a connected, planar graph whose number of vertices is a multiple of $8$. $5/8$ of the vertices have degree $3$, $1/4$ have degree $4$, and $1/8$ have degree $5$. All faces of $G$ are triangles or quadrilaterals. Find the number of triangular faces, the number of quadrilateral sides, the number of vertices and the number of edges of $G$. Draw at least one such graph.

It is a problem from an old exam. (I'm trying to prepare for mine.)

I've seen people solve problems like this using a formula that had some kind of a weighted sum in it (and I think the weights were degrees, probably of vertices), and it looked like it was linked to Euler's formula. I remember people saying that they were no-brainers, with an algorithmic procedure for solving them. Unfortunately I didn't understand the formula then, and I can't find it now, either in my notes or on the internet.

Could you please help me with this? I've been trying to derive something useful from what I know about Euler's theorem, but I'm failing badly.

share|improve this question
add comment

1 Answer

up vote 6 down vote accepted

From counting vertex-edge incidences, we have $$\tag1 2e = 3\cdot\frac58v+4\cdot\frac14v+5\cdot \frac18v=\frac72v.$$ From counting face-edge incidences, we have $$\tag2 2e = 3f_3+4f_4.$$ From Euler's $v+f=e+2$, we have $$\tag3 v+f_3+f_4=e+2.$$ Thus $7(3)$ gives us using $(1)$: $ 7e+14=7v+7f_3+7f_4=4e+7f_3+7f_4=6e+4f_3+3f_4$ or $$ e=4f_3+3f_4-14.$$ Using $(2)$ again, we find $3f_3+4f_4=2e=8f_3+6f_4-28$ or $$ 5f_3+2f_4=28.$$ As $f_3,f_4\ge0$, this allows only $(f_3,f_4,e,v)\in\{(0,14,28,16),(2,9,21,12),(4,4,14,8)\}$. An example with the tlast tuple is obtained by taking a cube graph and adding two face diagonals with a common end point (that assume degree 5 this way). Rereading the original problem statement (as opposed to equation $(1)$ we obtained from it), we see that $v$ must be a multiple of $8$, hence $(2,9,21,12)$ does not work.


Alright, "pics, or it didn't happen": enter image description here

share|improve this answer
    
Thank you very much! It didn't occur to me to use the handshaking lemma for faces and edges. To have a complete solution though, shouldn't I prove or disprove that each of the three tuples can be realized by a planar connected graph? To do that, do I just have to find examples, or is it possible to prove that such graphs exist in some other, simpler way? –  Bartek Jun 10 '13 at 22:12
    
@Bartek Yes, for completeness the existence of realizations needs to be shown (or disproved). I did that for one and a half case only. –  Hagen von Eitzen Jun 11 '13 at 6:27
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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