Whitney proved long ago that every maximal planar graph with no separating triangles is Hamiltonian. However, the converse is not necessarily true, that is, there exist maximal planar graphs that are hamiltonian and have separating triangles. So what happens when a maximal planar graph has separating triangles? Is there still some condition under which we can say with certainty that it will be Hamiltonian as well?
One theorem of this kind was shown by Jackson and Yu.
Consider a maximal planar graph with a separating triangle . can be decomposed into two graphs and such that and . If or still has separating triangles, then decompose them similarly. Eventually, we will be left with a collection of maximal planar graphs without any separating triangles. Now, consider a graph whose nodes represent elements of the set and there is an edge between two nodes if they share a separating traingle in . Let’s call this graph . The theorem by Jackson and Yu states that if has maximum degree 3, then is Hamiltonian.
This way of decomposing maximal planar graphs has been popular. It was first used by William Cunningham and Jack Edmonds in 1980. They proved several interesting results about the decomposition graph .