A sufficient condition for planar graph

705 Views Asked by At

Let $G$ a graph with $v$ vertices and $e$ edges. Right, I know that if $e>3v-6$ then $G$ is not planar. Do you know any theorem like "If $e<f(v)$ then $G$ is planar"?

1

There are 1 best solutions below

0
On

I want to report an error (I think) in the book "Graph Theory with applications", by C. Vasudev, New Age International Publishers Chapter 2, Problem 2.15. Find a graph G with degree sequence [4,4,3,3,3,3] such that G is not planar.

Solution. It is not possible to draw such a non planar graph because $$2e=4+4+3+3+3+3=20$$$$e=10$$ and the inequality $$e \leq 3v-6$$ does not hold.

It is false. The graph G:={{1, 3}, {1, 4}, {1, 5}, {1, 6}, {2, 4}, {2, 5}, {2, 6}, {3, 4}, {3, 5}, {3, 6}} has 6 vertices, 10 edges, the degree sequence [4,4,3,3,3,3] and it is not planar. The author uses the wrong theorem "If $$e \leq 3v-6$$ then G is planar."