5. Паук сплёл паутину, как показано на рисунке. Какое наибольшее количество нитей паутины можно перерезать, чтобы паутина не распалась на части?

Паутина представляет собой граф. Чтобы паутина не распалась на части, необходимо сохранить связность графа. Максимальное количество нитей, которое можно перерезать, равно общему количеству нитей минус количество нитей, образующих минимальное остовное дерево. На рисунке 8 нитей. Минимальное остовное дерево для данного графа будет иметь 5 нитей (4 вершины, 8 ребер). Следовательно, можно перерезать 8 - 5 = 3 нити.