Complete Graph Immersions from Minimum Degree

Definitions and mathematical statement

For the conventional interpretation using nonempty finite simple undirected graphs, let $d_G(v)$ be the number of neighbors of $v$, and let $\delta(G)=\min_{v\in V(G)}d_G(v)$. Let $K_n$ denote the complete simple graph on $n$ vertices. A weak immersion of $K_n$ in $G$ consists of an injective map $\phi:V(K_n)\to V(G)$ and, for each edge $uv\in E(K_n)$, a path $P_{uv}$ in $G$ joining $\phi(u)$ to $\phi(v)$, such that these paths are pairwise edge-disjoint. Their vertices may overlap. A strong immersion additionally requires that no internal vertex of any $P_{uv}$ belongs to $\phi(V(K_n))$.

Question under these conventions. Is it true that, for every integer $n\geq 1$ and every nonempty finite simple undirected graph $G$, \[ \delta(G)\geq n \quad\Longrightarrow\quad G\text{ contains a weak immersion of }K_n? \] For $n=1$, the immersion data consist of one chosen vertex and no paths; this boundary value is retained from the source.

Unresolved source qualifications. The supplied statement says only "graph" and "immersion." It does not explicitly specify finiteness, simplicity, or whether weak or strong immersion is intended. Consequently, the displayed formulation is an explicit conventional interpretation requiring confirmation against the source, rather than a verified determination of those missing conventions. The background's reference to strong immersions does not by itself specify the immersion notion in the question. The degree threshold in the question is exactly $n$, not $n-1$.

Short English statement

The question asks whether every graph with minimum degree at least $n$ contains $n$ distinct branch vertices joined pairwise by edge-disjoint paths representing $K_n$, for every integer $n\geq1$. The intended graph class and whether these paths must also satisfy the strong-immersion condition require confirmation. The supplied registry labels the problem open.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30003026$, titled Complete Graph Immersions from Minimum Degree; exact source problem code catalogue entry. The record belongs to the Oberwolfach Reports Open Problems collection and gives proposed year 2016; no individual proposer is identified.
• Supplied report attribution: Graph Theory (2016), Oberwolfach Reports, DOI 10.4171/owr/2016/2, pp. 51--86. https://doi.org/10.4171/owr/2016/2. The supplied background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions.
• Supplied literature reference: Dvorak and Yepremyan, Complete graph immersions and minimum degree. https://arxiv.org/abs/1512.00513.
• Supplied literature reference: Collins and Heenehan, Constructing graphs with no immersion of large complete graphs. https://arxiv.org/abs/1206.1545.
• Supplied literature reference: Oberwolfach Report 2/2016. https://doi.org/10.4171/owr/2016/2.
• Literature assessment dated exactly 2026-08-21: supplied dated curation, not independently verified. It labels the exact minimum-degree-at-least-$t$ immersion question open, reports strong $K_t$ immersions from minimum degree $11t+7$, and states that constructions at degree $t-1$ do not refute the degree-$t$ statement. These are supplied literature claims, not mathematical conclusions verified in this draft. The background explicitly requests independent verification of time-sensitive status and cited claims.
• The supplied statement-status label is corrected_verified; its accompanying verification note reports only notation, typography, and TeX-delimiter cleanup, with hypotheses, quantifiers, and subquestions preserved. This label does not establish independent mathematical verification here.