![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/9/97/Graceful_labeling.svg/languk-640px-Graceful_labeling.svg.png&w=640&q=50)
Граціозна розмітка
вершинна розмітка графу з m ребрами підмножиною цілих чисел між 0 і m включно, така, що різні вершини позначено різними числами, а абсолютна р / З Вікіпедії, безкоштовно encyclopedia
Граціозна розмітка[1] в теорії графів — така вершинна розмітка графу з ребрами деякою підмножиною цілих чисел між 0 і
включно, що різні вершини позначено різними числами, і така, що, якщо кожне ребро позначити абсолютною різницею міток вершин, які воно з'єднує, то всі отримані різниці будуть різними[2]. Граф, який допускає граціозну розмітку, називають граціозним графом.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/9/97/Graceful_labeling.svg/320px-Graceful_labeling.svg.png)
Автором терміна «граціозна розмітка» є Соломон Ґоломб; Александер Роса був першим, хто виділив цей клас розміток і ввів його під назвою -розмітка в статті 1967 року про розмітки графів.[3].
Однією з головних недоведених гіпотез у теорії графів є гіпотеза граціозності дерев (англ. Graceful Tree Conjecture), також відома як гіпотеза Рінгеля — Коціга за іменами її авторів Герхарда Рінґеля[ru] і Антона Коціга[en], яка стверджує, що всі дерева граціозні. Станом на 2017 гіпотезу все ще не доведено, але простота формулювання привернула широку увагу математиків-аматорів (внаслідок чого з'явилося багато неправильних доведень), Коціг свого часу навіть охарактеризував масові спроби довести її як «хворобу»[4].