Turkey NMO 2002 problem3

[drago]

Една задача от турска олимпиада, на която не и знам решението.
http://www.artofproblemsolving.com/Foru ... 1&t=446932

Даден е свързан граф G, всеки негов връх има валенция(степен) поне 3.
Да се докаже, че част от ребрата му могат да се изтрият, така че новия граф също да е свързан и поне 2/9 от върховете му да имат валенция 1.

[drago]

В "J. A. Storer, Constructing full spanning trees for cubic graphs, Inform. Process. Lett.
13 (1981)" е построен алгоритъм и е доказана оценка отдолу за броя на "листата" (върховете с валенция 1), които остават при подходящо премахване на част от ребрата и тя е [tex]\lfloor \frac{n}{4} \rfloor + 2[/tex], което е по-добро от оценката в тази задача.
Това изостря още повече любопитството ми за авторовото решение, все пак е давана на нац. кръг на олимпиада !

[drago]

Тъй като задачата силно ме заинтригува, попрочетох малко писаното в нета. Алгоритъмът, описан от Storer не е сложен, за доказателството на оценката той използва една хитра cost функция, която не намалява на всяка стъпка. Намерих малко по различен подход за доказване на същото. Който е любопитен може да го прочете тук:
http://www.artofproblemsolving.com/Foru ... 8#p2563088