О деревьях радиуса 2 с максимальным количеством паросочетаний

Паросочетанием в графе называется любое множество его попарно не смежных ребер. В настоящей статье рассматривается и решается задача максимизации количества паросочетаний в деревьях радиуса не более чем 2 с заданным количеством вершин. Было выявлено, что для любого $n\ge 56$, где $n=3k+r$, $k\in{\mathbb N},r\in \{0,1,2\}$, экстремальное дерево единственно; оно получается соединением вершины с центральными вершинами в $b$ копиях 3-пути и с листовыми вершинами в $a$ копиях 2-пути, где $b = k+\dfrac{r - 1 - 2a}{3}$, $(r,a)\in \{(0,1),(1,0),(2,2)\}$. Для любого $6\le n\le 55$ соответствующее экстремальное дерево тоже единственно (кроме $n=8$, когда имеется два таких дерева) и устроено подобным образом, при $1\le n\le 5$ единственным экстремальным деревом является путь на $n$ вершинах. Для доказательства этих фактов были предложены некоторые преобразования графов, увеличивающие количество паросочетаний и сохраняющие число вершин. Автор надеется, что данные преобразования будут полезны для решения аналогичных задач в других классах графов.