Какие существуют основные методы решения задач теории графов в олимпиадной математике?

Один из основных методов решения олимпиадных задач с использованием теории графов —  перевод условия задачи на математический язык. cyberleninka.ru В рамках этого метода объекты, рассматриваемые в задаче, принимаются за вершины графа, а отношения между ними изображаются рёбрами графа. cyberleninka.ru

Некоторые другие методы решения задач теории графов в олимпиадной математике:

• Использование алгоритмов на графах. cyberleninka.ru infourok.ru К ним относятся, например, алгоритм поиска в ширину, алгоритм двунаправленного поиска, метод накопления. cyberleninka.ru infourok.ru
• Применение метода графового моделирования. cyberleninka.ru Он применим, если условие задачи удовлетворяет определённым критериям: существование объектов и отношений между ними, которые можно изобразить вершинами и рёбрами графа, комбинаторный характер задачи, возможность изучения структурных связей между объектами. cyberleninka.ru
• Использование свойства чётности суммы степеней всех вершин графа. rep.bntu.by dzen.ru Так как каждое ребро считается дважды (для одной и для второй вершины), то сумма степеней всех вершин графа должна быть чётным числом. dzen.ru
• Применение метода от противного. dzen.ru Например, в задаче, где нужно доказать, что из столицы можно долететь в город Дальний (возможно, с пересадками), предполагается, что из столицы нельзя попасть в Дальний, и на основе этого делается вывод о возможности полёта. dzen.ru