TOPICS
Search

Grinberg Formula


A formula satisfied by all Hamiltonian cycles 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

 [# regions in interior]=d+1=f_2+f_3+...+f_n.
(1)

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

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

Take (2) minus 2×(1),

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

Similarly,

 g_3+2g_4+...+(n-2)g_n=n-2,
(4)

so

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

Explore with Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Grinberg Formula." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GrinbergFormula.html

Subject classifications