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.

Suppose that a connected planar simple graph with $e$ edges and $v$ vertices contains no simple circuit with length greater than or equal to $4.\;$ Show that $$\frac 53 v -\frac{10}{3} \geq e$$

or, equivalently, $$5(v-2) \geq 3e$$

share|improve this question
2  
Please refrain from ordering us to answer questions, also if this is homework, please tag it as such. –  Nicolas Villanueva Jun 20 '11 at 15:48
1  
I believe I've seen this before, just can't remember the proof off the top of my head, but $$5 \cdot v - 10 \geq 3 \cdot e$$ definitely looks familiar O_o... –  Nicolas Villanueva Jun 20 '11 at 15:55
3  
@Nicolas: this is Thomas's first post. It is fine to provide the "lay of the land" regarding the site's protocols...but when a user is new, this can be done in a more welcoming manner! @Thomas: Although a lot of math problems, particularly homework or exercise statements, use the "imperative" (Show...Prove...Calculate...etc), we generally prefer that questions be questions: "how do I..." "what does this mean?..." "Why is ___ true?" etc... –  amWhy Jun 20 '11 at 16:15

2 Answers 2

As Joseph suggests, one of two formulas you'll want to use for this problem is Euler's formula, which you may know as

$$r = e - v + 2 \quad\text{(or}\quad v + r - e = 2)\qquad\qquad\quad (1)$$

where $r$ is the number of regions in a planar representation of $G$ (e: number of edges, v: number of vertices). (Note, for polyhedra which are clearly not planar, this translates into $r = F$, where $F$ is the number of faces of a polyhedron.)

Now, a connected planar simple graph drawn in the plane divides the plane into regions, say $r$ of them. The degree of each region, including the unbound region, must be at least five (assuming graph $G$ is a connected planar graph with no simple circuit with length $\leq 4$).

For the second formula you'll need: remember that the sum of the degrees of the regions is exactly twice the number of edges in the graph, because each edge occurs on the boundary of a region exactly twice, either in two different regions, or twice in the same region. Because each region $r$ has degree greater than or equal to five, $$2e = \sum_{\text{all regions}\;R} \mathrm{deg}(R) \geq 5r\qquad\qquad\qquad\qquad (2)$$

which gives us $r \leq \large\frac 25 e$.

Now, using this result from (2), and substituting for r in Euler's formula, (1), we obtain $$e - v + 2 \leq \frac 25 e,$$ $$\frac 35 e \leq v - 2,$$ and hence, we have, as desired: $$e \leq \frac 53 v - \frac {10}{3} \quad\iff \quad \frac 53 v - \frac{10}{3} \geq e \quad \iff \quad 5(v-2) \geq 3e$$

share|improve this answer

Try using Euler's "polyhedral formula" - If G is a connected plane graph then V + F - E = 2.

share|improve this answer

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.