Какое наибольшее число верёвочек, соединяющих соседние узлы сетки размера 4x6, можно разрезать, чтобы сетка не распалась на отдельные куски?

Ответ: Поскольку горизонтальных отрезков 5*6 = 30, а вертикальных - 7*4 = 28, то всего верёвочек 30+28 = 58. Далее, узелков 5*7 = 35. Поскольку во всяком дереве количество рёбер на 1 меньше количества вершин (см. здесь http://ru.wikipedia.org/wiki/Дерево_(теория_графов)), то останутся неразрезанными 35–1 = 34 верёвочек. Соответственно, будут разрезаны 58–34 = 24 верёвочки.