Каркасне дерево зберігає всі мости й викидає рівно одне ребро з кожного незалежного циклу, причому вибір у різних двозв'язних компонентах (блоках) незалежний. Тому мультимножина степенів стала тоді й лише тоді, коли її не змінює жоден блок окремо: якщо якийсь блок дає два різні результати, зафіксувавши вибір у решті блоків, ми одразу отримаємо два каркасні дерева з різними мультимножинами.
Розберемо, які блоки нічого не змінюють.
Міст. Вибору немає — підходить завжди.
Цикл. Викидається рівно одне ребро, і воно зменшує на одиницю степені двох своїх кінців. Результат не залежить від вибору тоді й лише тоді, коли для всіх ребер циклу невпорядкована пара \{\deg u, \deg v\} однакова. (Це саме рівність пар: якщо позначити зміну мультимножини твірною функцією, рівність -(t^x + t^y) + (t^{x-1} + t^{y-1}) для двох пар після скорочення на 1 - t дає t^{x-1} + t^{y-1} = t^{p-1} + t^{q-1}.) Наприклад, підходить цикл, усі вершини якого мають однаковий степінь, або цикл парної довжини зі степенями, що чергуються.
Будь-який інший блок — у ньому ребер більше, ніж вершин, і серед його каркасів завжди є два з різними степенями.
Отже: знайти блоки (звичайний пошук у глибину зі стеком ребер), перевірити, що кожен — міст або цикл (кількість ребер дорівнює кількості вершин блоку), і що всі ребра кожного циклу з'єднують однакову пару степенів. Степені беруться у вихідному графі, а не всередині блока.
Складність: O(n + m).
Для цього етапу офіційного розбору опубліковано не було; цей текст написано для архіву за розв'язком, який перевірено на задачі.