A Criterion for Planar Graphs

It is difficult to know in general when a graph has a planar embedding without actually seeing a planar embedding. However, we can derive a necessary criterion for planarity using Euler’s characteristic formula, depending only on the number of vertices and edges of the graph (making it independent of any particular planar embedding). By contrapositive, we get a sufficient criterion for non-planarity.