Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|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

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.

share|cite|improve this answer

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.