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

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!

-

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.

-
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