С тех пор, как я собрал серию пластинок "На концертах Владимира Высоцкого", меня интересовал вопрос: планарен ли её граф?
То есть: можно ли все песни Высоцкого и все пластинки из этой серии расположить на плоскости таким образом, чтобы каждая пластинка была связана нитями с песнями, которые в неё вошли, и чтобы эти нити не пересекались.
Сегодня я наконец нашёл время добить эту задачу. Ответ - нет, не планарен!
Доказательство - применение критерия Понтрягина-Куратовского. Граф, в котором есть подграф "три дома и три колодца" планарным быть не может, и такой подргаф действительно есть.

Три дома: 1, 10, 19.
Три колодца: 5, 6, 9.
(Или наоборот, это все равно.)
1 - "Мой друг уехал в Магадан" - 12 - "Моим друзьям" - 5
1 - "Братские могилы" - 3 - "Солдаты группы Центр" - 13 - "Утренняя гимнастика" - 6
1 - "Песня о друге" - 4 - "О переселении душ" - 9
10 - "Тот, который не стрелял" - 17 - "Лошадей двадцать тысяч" - 5
10 - "Марафон" - 6
10 - "Милицейский протокол" - 9
19 - "Моя цыганская" - 5
19 - "Про любовь в каменном веке" - 6
19 - "Ноты" - 8 - "Сыт я по горло" - 9
Вот эти девять нитей никак нельзя расположить на плоскости так, чтобы они не пересекались!
Примечание: песня "Братские могилы" фактически имеется и на пластинке 13, но не обозначена в описании. Поэтому нить 2 можно сделать и короче, если не придираться к этому моменту.