Proving Planarity of a graph

73 Views Asked by At

I know the condition to be planar graph is that $E \leq 3V − 6$, so if we have a graph where the number of edges is smaller than $3\cdot (vertices) − 6$, can we say its planar? If not, how would I go about proving that a graph is planar? (other than using Kuratowski's Theorem)

1

There are 1 best solutions below

0
On

The Petersen graph is non-planar and has $10$ vertices and $15$ edges. The inequality $E\leq 3V-6$ is not a "condition for a graph to be planar." It is a property of planar graphs. That is, any planar graph will satisfy this inequality, but as the example shows, there are non-planar that satisfy it also.