Некоторые математические головоломки, которые можно решить с помощью теории графов:

• Задачи о рисовании фигур одним росчерком. 1 Например, нужно начертить разные варианты конверта или квадрат с диагоналями и четырьмя дугами, не отрывая карандаша от бумаги и не проводя по одной линии дважды. 1
• Задача о семи кёнигсбергских мостах. 1 Нужно найти путь по дорогам или мостам, который будет проходить по всем дорогам (мостам) ровно по одному разу. 1
• Задача о доме из пяти комнат. 1 Каждая комната соединена с другой и с улицей дверьми. 1 Необходимо найти такой путь по комнатам, который проходил бы по всем 16 дверям ровно по одному разу (начинать и заканчивать можно в любой комнате или вне дома). 1
• Головоломка «Домики и колодцы». 4 Нужно нарисовать на рисунке три дома, выстроенных в ряд, и три отдельных «колодца» (с водой, газом и электричеством). 4 Задача состоит в том, чтобы нарисовать на этом рисунке линии, соединяющие три колодца с каждым домом. 4 При этом ни одна из линий (всего девять) не должна пересекаться с другими. 4