Здравейте,
Получих запитване относно въпрос № 14. А именно,
какво се разбира под "теорема за броя на ребрата".
Тази теорема я няма в учебника, а не лекции пропуснах
да я спомена в явен вид като отделна теорема (макар
че д-вото на МПД свойството я ползва).
Теоремата казва, че ако към дърво G добавим едно
ребро, получаваме граф с точно един цикъл. Доказва
се тривиално с допускане на противното. Забележете,
че ако G е граф изобщо (а не именно дърво), добавянето
на едно ребро може да доведе до появата на > 1 цикли,
така че теоремата има смисъл.
Накратко, тази теорема отпада от въпрос № 14. Естествено,
ако някой я формулира и докаже, това ще плюс за писмената
му/и работа.
Поздрави,
ММ