Can anyone give an example for this theorem related to planar graphs?

212 Views Asked by At

Theorem:

Let $G$ be a connected planar graph with $p$ vertices and $q$ edges, where $p\geq 3$. Then $q\leq3p-6$.

Proof: Let $r$ be the number of regions in a planar representation of $G$. By Euler's formula:

$p-q+r=2$

The sum of the degrees of the regions equals $2q$ . But each regions has degree $3$ or more, hence

$2q\geq3r$.

Question is, from where does the inequality come from?

No matter how many connected, planar graphs I draw, I always get $2q = 3r$. Can someone give me a graph or a case where $2q>3r$?

2

There are 2 best solutions below

5
On BEST ANSWER

any planar connected graph that has a region with degree 4 or more, and without pendant nodes


Note: "The sum of the degrees of the regions equals $2q$" is false, because you could have some edge that belongs to only one region (for example in the star graph).

But it's true that the sum of the degrees of the regions is greater or equal to $3r$, and less or equal to $2q$, so the theorem is still correct.

0
On

The cycle $C_n$ for $n\geq 4$. Then $q=n$ but $r=2$ and certainly $2n>6$.