Highly connected graphs with no K_n minor

Definitions and mathematical statement

For an integer $t\ge5$, a graph is $t$-vertex-connected if it has more than $t$ vertices and deleting any fewer than $t$ vertices leaves it connected. All graphs here are finite and simple. A $K_t$ minor is specified by $t$ disjoint nonempty connected vertex sets, called branch sets, with an edge between every two branch sets. Contracting each branch set and deleting surplus edges yields the complete graph $K_t$.

The conjecture asks whether, for every integer $t\ge5$, there exists an integer $N(t)$ such that every $t$-vertex-connected graph $G$ with $|V(G)|\ge N(t)$ and no $K_t$ minor has a set $S\subseteq V(G)$ satisfying \[ |S|\le t-5,\qquad G-S\text{ is planar}. \] Planar means that the graph has a drawing in the plane with no crossings between edge interiors. The set $S$ is allowed to depend on $G$, while the order threshold depends only on $t$. The parameter $t$ is the connectivity and excluded-minor parameter, not the order of $G$.

For $t=5$ the deletion set must be empty. For larger $t$, the claim is that sufficiently large examples are obtained from planar graphs by adding at most $t-5$ exceptional vertices, whose incidences need not satisfy any further restriction. The sufficiently-large-order qualification is part of the assertion and must not be replaced by a claim covering every order.

Short English statement

For each fixed connectivity t, are all sufficiently large t-connected graphs without a complete t-vertex minor planar after deleting at most t−5 vertices?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3183 (OPG-153), OpenGarden. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Highly connected graphs with no K_n minor. Original problem and discussion. http://www.openproblemgarden.org/op/high_connectivity_no_k_n.