13. Нужно изготовить каркасную модель куба заданного размера с диагональю (см. рисунок), затратив минимальное количество проволоки. Проволоку можно гнуть в точках соединения. Какое наименьшее количество кусков проволоки нужно, чтобы изготовить модель, указанную на рисунке?

Рассмотрим каркас как связный граф: вершины куба — точки соединения, рёбра — участки проволоки. На рисунке к 12 рёбрам куба добавлена одна диагональ.

1. У куба степень каждой вершины равна 3. Концы добавленной диагонали получают степень 4, остальные шесть вершин остаются нечётными.

2. Один непрерывный кусок проволоки может пройти по рёбрам как маршрут, у которого нечётных вершин не больше двух. Чтобы покрыть все рёбра, при наличии шести нечётных вершин нужно как минимум три маршрута, то есть три куска.

3. Трёх кусков достаточно: рёбра связного графа можно разбить на три маршрута, попарно соединяя шесть нечётных вершин.

Ответ: 3 куска проволоки.