= Four-connected planar obstruction to two-linkage
On vertices $0,\ldots,7$, join cyclic indices differing by one or two modulo eight. The resulting <planar graph> has a square face bounded in order by $0,2,4,6$. 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 $0$ to $4$ and $2$ to $6$ would cross in the complementary disk of the square face, contrary to the <Jordan curve theorem>. Thus four-connectivity does not guarantee two-linkage.
Back to article page
