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.

I am a first year math student, and I'm studying some exercises for my graph theory exam. This exercise I didn't understand very well:

Let $G$ be a planar (simple) graph with $m (≥2)$ edges and $f$ faces. Prove that $f ≤ \frac{2}{3} m$.

If I look at examples this make sense, but I find it hard to prove it. In algebra or analysis I'm used to prove something from other theorems, but here it seems like I need to prove it really out of nothing.

This is an example I can find where $3f=2m$:

enter image description here

And now, if I add more lines, I can't get examples that disprove it, but I find it hard to reason why this is true. Any hints ?

share|improve this question
    
@Kasper By facets you probably mean faces. Are you aware of Euler's Formula? Moreover, if the graph has at least 2 edges, what is the minimum number of vertices it can have? –  user39280 May 11 '13 at 10:14
1  
@dado The Euler formula is introduced exactly after this exerise. So yes, I'm aware of it, but I think I need to prove this without that theorem. –  Kasper May 11 '13 at 10:18
add comment

2 Answers

up vote 3 down vote accepted

Put a pebble on each side of each edge. Each face will have at least $3$ pebbles (why?), so number of pebbles is at least $3$ times number of faces, but also each edge has $2$ pebbles, so number of pebbles is twice number of edges.

share|improve this answer
1  
I love your explanation. So you need at least three lines to enclose a face. So that is at least 3 pebbles. For the face that is not enclosed you have two options: Or there is a three like graph, and as $m ≥2$ you will get at least 4 pebbles. Or there is no three, and then you have at least 3 pebbles. –  Kasper May 11 '13 at 10:30
add comment

No need to use Euler's formula.

Hint: You know that the sum of the degrees of all vertices is $2m,$ and each face consists of at least three vertices.

share|improve this answer
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.