Существование неприводимых мультиобходов кратности $2$

Ивановым и Тужилиным была предложена одномерная проблема Громова о минимальном заполнении конечных метрических пространств, где в качестве заполнений рассматриваются взвешенные графы с неотрицательными весами ребер. Они показали, что задача редуцируется к случаю так называемых бинарных деревьев — деревьев у которых вершины имеют только степени $1$ и $3$. Ерёминым была получена минимаксная формула веса минимального заполнения. Формула Ерёмина использует понятие минимального параметрического заполнения — фиксируется граф (параметризация или тип); он показал, что вес минимального параметрического заполнения равен максимальному значению так называемого мультипириметра среди всех неприводимых мультиобходов.
Сложность структуры бинарного дерева можно измерять количеством так называемых усов — пар граничных вершин с общей смежной вершиной. Настоящая работа посвящена изучению мультиобходов бинарных деревьев с тремя усами. Найдена линейная рекуррентная формула для числа бинарных деревьев с тремя усами. Установлена связь между неприводимостью мультиобходов и включениями мультиграфов мультиобходов для фиксированного бинарного дерева.
Недавно Щербаковым было доказано, что кратность неприводимого мультиобхода для бинарного дерева с тремя усами не превосходит $2$, в этой работе доказано существование таких неприводимых мультиобходов у любого такого бинарного дерева.
Недавно Иванов и Тужилин предложили вычислять вес минимального параметрического заполнения, находя вершины многомерного многогранника допустимых значений переменных двойственной задачи линейного программирования с помощью компьютера. Разработанная в настоящей работе техника позволяет найти все неприводимые мультиобходы у бинарного дерева с $6$ граничными вершинами и $3$ усами без использования компьютерных вычислений.