Get Math Help

GET TUTORING NEAR ME!

(800) 434-2582

By submitting the following form, you agree to Club Z!'s Terms of Use and Privacy Policy

    Home / Get Math Help

    Grinberg Formula

    Definition

    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. Any region with j sides is bounded by j graph edges, so such regions contribute j f_j to the total. However, this counts each diagonal twice (and each graph edge only once). Therefore, 2f_2 + 3f_3 + ... + n f_n = 2d + n.

    Associated person

    Emanuels Donats Frīdrihs Jānis Grinbergs

    Back to List | POWERED BY THE WOLFRAM LANGUAGE