Planarity Edge Bound Check

Problem

Check the basic necessary density condition for planarity of a simple graph: E <= 3V - 6 when V is at least 3.

A graph violating this bound cannot be planar, while passing it does not guarantee planarity. n is the number of nodes and edges is a list of [u, v] pairs. Return a boolean.

Hint

K5 needs 10 edges while the planar bound allows only 9.

Test cases

case 1

in: [4,[[0,1],[0,2],[0,3],[1,2],[1,3],[2,3]]]

expected: true

case 2

in: [5,[[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]]

expected: false

case 3

in: [2,[[0,1]]]

expected: true

case 4

in: [6,[[0,3],[0,4],[0,5],[1,3],[1,4],[1,5],[2,3],[2,4],[2,5]]]

expected: true

Starter codePython

def planarity_edge_bound(n, edges):
    # Your code here
    pass

4 test cases · run your code against them in the editor