Grinberg Formula

A formula satisfied by all Hamiltonian Circuits with $n$ nodes. Let $f_j$ be the number of regions inside the circuit with $j$ sides, and let $g_j$ be the number of regions outside the circuit with $j$ sides. If there are $d$ interior diagonals, then there must be $d+1$ regions

$$\hbox{[\char93 regions in interior]} = d+1=f_2+f_3+\ldots+f_n.$$ (1)

Any region with $j$ sides is bounded by $j$ Edges, so such regions contribute $jf_j$ to the total. However, this counts each diagonal twice (and each Edge only once). Therefore,

$$2f_2+3f_3+\ldots+nf_n=2d+n.$$ (2)

Take (2) minus $2\times$(1),

$$f_3+2f_4+3f_5+\ldots+(n-2)f_n=n-2.$$ (3)

Similarly,

$$g_3+2g_4+\ldots+(n-2)g_n=n-2,$$ (4)

so

$$(f_3-g_3)+2(f_4-g_4)+3(f_5-g_5)+\ldots+(n-2)(f_n-g_n)=0.$$ (5)