Prime Labelings of Trees

Definitions and mathematical statement

For a finite graph $G=(V,E)$ of order $n=|V|\geq 1$, a prime labeling is a bijection \[ f:V\longrightarrow\{1,\ldots,n\} \] such that \[ \gcd\left(f(u),f(v)\right)=1 \qquad\text{for every }\{u,v\}\in E. \] The graph is called prime if it admits such a labeling; this terminology does not require the individual vertex labels to be prime numbers.

Using the standard convention that a tree is a nonempty finite simple undirected connected acyclic graph, the supplied question is: \[ \begin{gathered} \text{For every integer }n\geq 1\text{ and every tree }T=(V,E)\text{ with }|V|=n,\\ \text{does there exist a bijection }f:V\longrightarrow\{1,\ldots,n\}\\ \text{such that }\gcd\left(f(u),f(v)\right)=1 \text{ for every }\{u,v\}\in E? \end{gathered} \] For $n=1$, the adjacency condition is vacuous. The source does not explicitly specify graph conventions or whether an empty tree is permitted; the convention used above is therefore stated explicitly.

The supplied record labels the problem partially_solved, but its accompanying literature assessment concerns the graceful tree conjecture and graceful labelings. That assessment does not establish the status of the prime-labeling question stated here. The intended connection, if any, remains unresolved.

Short English statement

Can the vertices of every finite tree with $n$ vertices be assigned the integers $1,\ldots,n$, each exactly once, so that the labels at the ends of every edge are coprime? The supplied literature assessment discusses graceful labelings, so its relevance to this question requires review.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30001668$, title Prime Labelings of Trees, exact source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. The record gives proposed year 2011 and supplies no named proposer.
• Supplied report citation: Combinatorics (2011), Oberwolfach Reports, pp. 5--83, DOI 10.4171/owr/2011/01. Source URL and literature-source label "Oberwolfach problem statement": https://doi.org/10.4171/owr/2011/01.
• Supplied literature source labeled "Gallian survey": https://www.combinatorics.org/files/Surveys/ds6/ds6v8-2003.pdf.
• Supplied literature source labeled "current conjecture status": https://mlelarge.github.io/graph-conjectures/op/graceful_tree_conjecture/.
• Literature assessment checked at 2026-08-21: this is supplied dated curation derived from the OWR curation, not an independently verified assessment. It labels the record partially solved and states that the graceful tree conjecture remains open in general while many special tree classes, including "several listed here," are known to be graceful. No such list is present in the supplied record, and the assessment concerns a different labeling property from the stated prime-labeling question. The source itself requests independent verification of time-sensitive status and cited claims.
• The supplied statement status is corrected_verified; its verification note describes only enclosing TeX notation in mathematical delimiters without changing mathematical content. This supplied label is not independent mathematical or source verification.