TransWikia.com

proof for $eleq 3(v-2)$ [Why does $d(f) geq 3$?]

Mathematics Asked on February 13, 2021

Here is the well known theorem, "For planar graph $G$, if $vgeq3$ then $eleq 3(v-2)$"

I’ve reviewed my discrete mathematics note, suddenly the question crossed my mind.

When we proving the $eleq 3(v-2)$ for planar graph, $G$. We used $d(f) geq 3$.

In my note, it told me the reason why does $d(f) geq 3$ is "each face is bounded by at least three edges, but each edge borders two faces."

When I first saw it, it was clear for me. But the time passed I doubt about that.

Because… Let me suggest the counter example below.

enter image description here

The above graph is planar graph and $v=3, e=2,f=1$. But the $d(f) lt 3$ (I.e. the face is not bounded three edges)

Still I’ve confused what the point did I mistake.

Any help would be appreciated.

One Answer

Your counterexample is discussed in this answer. Because the edges are boundaries of the same face, in the proof the "boundary of the face" has 4 edges (each edge is counted twice).

Correct answer by angryavian on February 13, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP