Euler Characteristic of Planar Graph

Problem

Compute the Euler characteristic of a planar graph from its vertex, edge, and face counts: V - E + F.

n is the number of vertices, edges is the edge list, and faces is the number of faces including the outer one. Return the integer value, which equals 2 for any connected planar graph.

Hint

Euler's formula is the oldest invariant in graph theory.

Test cases

case 1

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

expected: 2

case 2

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

expected: 2

case 3

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

expected: 2

case 4

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

expected: 2

Starter codePython

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

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