В условиях олимпиадных соревнований можно решать различные задачи с использованием графов, например:

• Задачи на раскраску. 1 Например, нужно раскрасить кружки в разные цвета так, чтобы любые два кружка, соединённые отрезком, были покрашены в разные цвета. 1
• Задачи о дружбе. 1 Нужно построить граф, в котором вершины будут соответствовать детям, а рёбра — их дружбе. 1 Затем необходимо определить минимальное число рёбер в указанном графе. 1
• Задачи о соединении телефонов. 3 Нужно рассмотреть граф, вершины которого соответствуют телефонам, а рёбра — соединяющим их проводам. 3 Затем необходимо подсчитать количество рёбер в этом графе и определить, возможно ли такое соединение. 3
• Задачи о маршрутах. 45 Например, нужно найти наименьшую сумму стоимостей всех авиаперелётов, если известно, что любой маршрут, начинающийся и заканчивающийся в одном городе, обойдётся в чётное число тысяч рублей. 4
• Задачи о туристах. 5 Нужно рассмотреть граф, в котором вершины — это города, а из каждого города проведён самый дорогой выходящий путь. 5 Затем необходимо определить, при каком наибольшем количестве дней возможно, чтобы через определённое время в каждом городе снова было по одному туристу и ни один не посетил никакой город дважды. 5