Grinberg Formula

A formula satisfied by all Hamiltonian cycles with  nodes. Let  be the number of regions inside the circuit with  sides, and let  be the number of regions outside the circuit with  sides. If there are  interior diagonals, then there must be  regions

(1)

Any region with  sides is bounded by  graph edges, so such regions contribute  to the total. However, this counts each diagonal twice (and each graph edge only once). Therefore,

(2)

Take (2) minus (1),

(3)

Similarly,

(4)

so

(5)