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.

I'm currently looking at two proofs to the following corollary to Euler's formula and I'm not quite seeing how the authors can make a specific assumption in their proof. One proof comes from my textbook, Introduction to Graph Theory by Robin J. Wilson and the other comes from Kent University about half-way down the page. They essentially say the same thing, just slightly different wording, so I'll refer to the latter because it's online.


Specifically, I have an issue with this:

Corollary 1: Let $G$ be a connected planar simple graph with $n$ vertices, where $n ≥ 3$ and $m$ edges. Then $m ≤ 3n - 6$.

Proof: For graph $G$ with $f$ faces, it follows from the handshaking lemma for planar graph that $2m ≥ 3f$ (why?) because the degree of each face of a simple graph is at least 3), so $f ≤ \frac{2}{3} m$.

Combining this with Euler's formula

$$Since ~~~~~~~~ n - m + f = 2$$ $$We ~~get ~~~~~~~~~~ m - n + 2 ≤ 2/3 m$$ $$Hence ~~~~~~~ m ≤ 3n - 6.$$



My issue is that the proof seems to assume too much. It states that the degree of each face of a simple graph is at least 3. How can that be assumed? As far as I'm concerned, that's not necessarily true. Suppose you had the following graph, a simple tree. It is still planar, connected, and simple; so every requirement holds.enter image description here Clearly there is just one face, the infinite face, and it is surrounded by just 2 edges; therefore it is not bounded by 3 or more edges as the proof claims. The degree of the infinite face is just 2 as far as I understand. Yet the corollary holds even for this graph. We get $ 2 \leq 3(3)-6$, which reduces to $ 2 \leq 3 $, which is valid. I'd appreciate if somebody could explain what's going on here. Thanks


One possibility I can think of is that since the infinite face touches both sides of the edges then it has degree 4 and not 2 as I mentioned earlier.

share|improve this question
add comment

2 Answers 2

up vote 2 down vote accepted

The linked-to notes were maybe a little unclear on this point, perhaps in the interest of not being too pedantic.

Anyway, for a given face $F$ of a connected plane graph, a boundary walk of $F$ is a closed walk that contains every edge on the boundary of $F$. This means that a boundary walk must start and stop at the same vertex.

The degree of a face is then defined to be the minimum possible length of a boundary walk of $F$.

So in your example, the infinite face actually has degree $4$, and I hope you can then convince yourself that if $n\geq 3$, any face has degree at least $3$.

share|improve this answer
    
Ah, ok. So if the walk is not closed then I need to count each edge twice, right? But yes, once this information is clear I should be able to convince myself of that. –  audiFanatic Apr 16 at 14:39
    
By definition, a boundary walk has to be closed. I think what you are thinking is that if you trace around the boundary of the face you'll encounter some edges which are bridges (edges whose deletion would disconnect the graph). These are the edges that need to be counted twice. –  Casteels Apr 16 at 14:47
    
Ah, ok; perfect! Thanks for the clear explanation! –  audiFanatic Apr 16 at 14:49
add comment

Exactly, because the infinite face touches both sides of the edges it has degree $4$. Since these edges are bridges we must count them twice, once for each side. Planar graphs have the property that if $n\geq3$, then $2m\geq3f$.

share|improve this answer
add comment

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.