未解决问题，组合数学与离散数学，1967年提出

优美树猜想

未解决

任意具有 $m = |V| - 1$ 条边的有限树 $T = (V, E)$ 都存在优美标号：即存在单射 $f: V \to \{0, 1, \dots, m\}$ ，使得每条边 $uv \in E$ 上诱导的边权 $|f(u) - f(v)|$ 互不相同，从而恰好取遍集合 $\{1, 2, \dots, m\}$ 。

研究前沿截至2026年

截至2026年，优美树猜想在一般情形下依然悬而未决。该猜想已对所有顶点数 $n \le 35$ 的树完成验证，并对路、毛毛虫树、对称树、橄榄树、蜘蛛树以及直径不超过 $5$ 的树等结构化树族获证。对于任意大规模树，概率方法与吸收技术已证明了若干渐近松弛结果——例如表明 $m$ 边树可用 $\{0, 1, \dots, (1 + o(1))m\}$ 中的标号实现无冲突差值标号，或作为彩虹树嵌入 $K_{2m+1}$ ——但彻底消除标号范围中的 $o(m)$ 误差项仍超出当前技术能力。

已知最佳结果

穷举计算机搜索已证实所有顶点数 $n \le 35$ 的树都是优美的（奥尔德雷德–麦凯于1998年验证至 $n \le 27$ ，方文杰于2010年验证至 $n \le 35$ ）。
路、毛毛虫树、叶节点不超过 $4$ 个的树、直径不超过 $5$ 的树、橄榄树以及对称树均已被证明在任意规模下都是优美的。
林格尔分解猜想对所有充分大的 $m$ 边树 $T$ 成立（蒙哥马利、波克罗夫斯基与苏达科夫，2020/2021），且有界度树允许取值于 $\{0, 1, \dots, (1 + o(1))m\}$ 的渐近优美标号。

使用的方法及其局限

方法	取得的结果	局限所在
归纳 $\alpha$ -赋值与树黏合构造	通过平移并拼接二分标号区间，为毛毛虫树、受限龙虾树、橄榄树以及直径不超过 $5$ 的树给出了显式的优美标号构造。	并非所有树都存在 $\alpha$ -赋值（例如某些含 $3$ 度顶点的树），且不规则分支会破坏归纳拼接所需的连续区间结构。
彩虹子图与分布式吸收法（蒙哥马利–波克罗夫斯基–苏达科夫）	在循环距离边染色下将任意充分大的 $m$ 边树嵌入为 $K_{2m+1}$ 的彩虹子图，从而对大 $m$ 彻底解决了林格尔猜想。	$\mathbb{Z}_{2m+1}$ 中的循环距离允许模 $2m+1$ 折返，而优美标号要求在 $\{0, 1, \dots, m\}$ 内不经模折返地精确实现绝对差。

尚未解决的问题

所有龙虾树（删去所有叶节点及其相邻顶点后化为一条路的树，贝尔蒙于1979年猜想其皆优美）是否都是优美的？
任意充分大的有界度 $m$ 边树 $T$ 是否都存在到 $\{0, 1, \dots, m\}$ 的精确优美标号？

参考文献

Alexander Rosa (1967). On certain valuations of the vertices of a graph
Joseph A. Gallian (2022). A dynamic survey of graph labeling
Richard Montgomery, Alexey Pokrovskiy, Benny Sudakov (2021). A proof of Ringel's conjecture · DOI:10.1007/s00039-021-00576-2 · arXiv:2001.02665