# 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

Lets use euler's theorem for this n-e+f=2 where:

n-vertices, e-edges and f-faces

Let $d_1,d_2,...,d_f$ where each $d_i$ is the number of edges in face $i$ of our grph. A cycle causes us to have a face, and according to this our smallest cycle is of size s $\Rightarrow |d_i| \geq s$

$d_1+d_2+...+d_f = 2e \Rightarrow s \times f\leq 2e\Rightarrow$ (f=2-n+e)

$2e\geq s(2-n+e)\Rightarrow 2e\geq 2s-sn+se\Rightarrow s(n-2) \geq e(s-2)$

Now just divide and you'll get the desired result.

-