Four-connected planar obstruction to two-linkage

ID: four-connected-planar-obstruction-to-two-linkage

On vertices , join cyclic indices differing by one or two modulo eight. The resulting planar graph has a square face bounded in order by . Deleting at most three vertices cannot disconnect it: each break in the surviving cyclic chain requires two consecutive deleted vertices, and two separate breaks require four deletions. It is therefore four-connected. Disjoint paths joining to and to would cross in the complementary disk of the square face, contrary to the Jordan curve theorem. Thus four-connectivity does not guarantee two-linkage.

New to topics? Read the docs here!