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)