Simpler Graph Conditions for Embedding Tetrahedral Meshes

Abstract

Three-dimensional Tutte-style embedding methods turn graph conditions into guarantees for tetrahedral meshes. Alexa's theorem excludes both K₆ and K₃,₃,₁ as graph minors and asks whether the second exclusion is necessary. We prove that it is redundant for a precisely defined class of topological-ball meshes. Let T be a finite simplicial complex whose realization is a closed topological 3-ball, and assume that every triangular face whose vertices all lie on the boundary is itself a boundary face. If the 1-skeleton G has no K₆ minor, then G is linklessly embeddable and hence has no K₃,₃,₁ minor.

The proof combines generic 4-rigidity and Jørgensen's extremal classification with a four-clique separator bound obtained from relative Alexander–Lefschetz duality. The Holst–Lovász–Schrijver clique-sum criterion then preserves linklessness throughout the resulting MP₁-cockade decomposition. A finite checker and a scoped Lean companion audit the local separator calculation and logical interfaces; the imported rigidity, extremal-minor, and linkless-embedding theorems remain external. The result assumes an actual topological ball and does not extend merely from simple connectivity.