Planar Graphs, Grinsberg's Formula

Grinsberg's Formula

Let a planar graph containing n vertices possses a hamiltonian circuit. Assume there are e edges inside the circuit, hence there are e+1 faces within the circuit. Let fi be the number of faces inside the circuit with i edges. The sum of i×fi counts the internal edges twice, and the circuit edges onces. Hence it is equal to 2e+n. At the same time, the sum of the faces is the number of edges + 1. double this and subtract from the first equation, whence the sum of (i-2)×fi = n-2.

Inside and outside are somewhat interchangeable, especially if you think of the circuit as running around the equator of a sphere. So we can derive an analogous equation for the faces gi on the outside of the circuit. specifically, the sum of (i-2)×gi = n-2. Subtracting the two equations gives sum (i-2)×(fi-gi) = 0.

This isn't much to go on, but occasionally a graph will produce an equation that is arithmetically impossible, hence there is no hamiltonian circuit. If all the faces of a graph have an edge count that is 2 mod 3, except for one face with 7 edges, then the term (7-2)×1 = 5 cannot be balanced by the other terms, which are all multiples of 3.