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.

Given $G = (V,E)$, a planar, connected graph with cycles, where the smallest simple cycle is of length $s$. Prove: $|E| \leq \frac{s}{s-2}(|V|-2)$.

The first thing I thought about was Euler's Formula where $v - e + f = 2$. But I really could not connect $v$, $e$ or $f$ to the fact that we have a cycle with minimum length $s$.

Any direction will be appreciated, thanks!

share|improve this question

1 Answer 1

up vote 1 down vote accepted

This is a question of Grimaldi, Discrete and Combinatorial Mathematics, chapter 11 section 4 exercise 23,a.

You may read the last few pages of this section, if you still do not see I can give you the hint.

Good luck

The responce for the last comment:

Each edge is in the boundary of at most 2 faces. Then if you consider the sum of lengths of all faces in G, or regions, the total lenght is always less equal to 2$e$. And obviously, since $s$ is the smallest lenght, the sum of lengths is greater and equal to $sr$. Finally we have this: $2e \geq \sum deg(r_i) \geq sr$ where $deg(r_i)$ is the number of edges in the boundary of face.

share|improve this answer
I don't have an access to the book. –  TheNotMe May 30 '13 at 8:26
Ok, so observe that $2e \geq sr$, $r$ is region in your notation it is $f$, face. –  Ada May 30 '13 at 8:30
Why is $2|e| \geq sr$? –  TheNotMe May 30 '13 at 8:54
Thanks alot, appreciated. –  TheNotMe May 30 '13 at 9:35

Your Answer


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.