Bài toán mở, Tổ hợp và Toán rời rạc, nêu năm 1967

Giả thuyết cây duyên dáng

Còn mở

Mọi cây hữu hạn $T = (V, E)$ có $m = |V| - 1$ cạnh đều có một phép gán nhãn duyên dáng: một đơn ánh $f: V \to \{0, 1, \dots, m\}$ sao cho các trọng số cạnh cảm sinh $|f(u) - f(v)|$ với $uv \in E$ đôi một phân biệt và do đó phủ đúng tập $\{1, 2, \dots, m\}$ .

Hiện trạng nghiên cứu tính đến năm 2026

Tính đến năm 2026, giả thuyết cây duyên dáng vẫn còn mở trong trường hợp tổng quát. Giả thuyết đã được kiểm chứng cho mọi cây có $n \le 35$ đỉnh và được chứng minh cho các họ có cấu trúc như đường đi, cây sâu róm, cây đối xứng, cây ô liu, cây nhện và các cây có đường kính không quá $5$ . Với các cây lớn tùy ý, phương pháp xác suất và kỹ thuật hấp thụ đã chứng minh được các nới lỏng tiệm cận — chỉ ra rằng một cây $m$ cạnh có thể gán nhãn duyên dáng bằng các nhãn trong $\{0, 1, \dots, (1 + o(1))m\}$ hoặc nhúng thành cây cầu vồng trong $K_{2m+1}$ — nhưng việc triệt tiêu độ dư $o(m)$ trong miền nhãn vẫn vượt ngoài khả năng của các kỹ thuật hiện nay.

Kết quả tốt nhất đã biết

Mọi cây có $n \le 35$ đỉnh đều duyên dáng, được xác nhận bằng tìm kiếm máy tính vét cạn (Aldred–McKay 1998 cho $n \le 27$ ; Fang 2010 cho $n \le 35$ ).
Các đường đi, cây sâu róm, cây có tối đa $4$ lá, cây có đường kính tối đa $5$ , cây ô liu và cây đối xứng đã được chứng minh là duyên dáng với mọi kích thước.
Giả thuyết phân rã Ringel đúng cho mọi cây $T$ đủ lớn có $m$ cạnh (Montgomery, Pokrovskiy và Sudakov, 2020/2021), và các cây bậc bị chặn có phép gán nhãn duyên dáng tiệm cận vào tập $\{0, 1, \dots, (1 + o(1))m\}$ .

Công cụ và chỗ dừng

Công cụ	Đạt được	Chỗ dừng
Phép $\alpha$ -định giá quy nạp và ghép nối cây	Xây dựng tường minh các phép gán nhãn duyên dáng cho cây sâu róm, cây tôm hùm dạng hạn chế, cây ô liu và cây có đường kính không quá $5$ bằng cách dịch chuyển và dán các miền nhãn hai phía.	Không phải mọi cây đều có $\alpha$ -định giá (chẳng hạn một số cây có đỉnh bậc $3$ ), và sự phân nhánh bất quy tắc phá vỡ cấu trúc khoảng liên tiếp cần thiết để dán quy nạp.
Đồ thị con cầu vồng và kỹ thuật hấp thụ phân phối (Montgomery–Pokrovskiy–Sudakov)	Nhúng mọi cây $m$ cạnh đủ lớn thành một đồ thị con cầu vồng của $K_{2m+1}$ dưới phép tô màu theo khoảng cách vòng quanh, giải quyết hoàn toàn giả thuyết Ringel cho $m$ lớn.	Khoảng cách vòng quanh trong $\mathbb{Z}_{2m+1}$ cuộn lại theo modulo $2m+1$ , trong khi phép gán nhãn duyên dáng đòi hỏi hiệu tuyệt đối chính xác trên $\{0, 1, \dots, m\}$ không được cuộn modulo.

Câu hỏi còn mở

Mọi cây tôm hùm (cây mà sau khi xóa các lá và các đỉnh kề lá thì còn lại một đường đi, được Bermond phỏng đoán là duyên dáng năm 1979) có đều duyên dáng hay không?
Liệu mọi cây bậc bị chặn $T$ đủ lớn có $m$ cạnh có luôn tồn tại một phép gán nhãn duyên dáng chính xác vào $\{0, 1, \dots, m\}$ hay không?

Tài liệu tham khảo

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