Любая математическая структура становится полезной для информатики только тогда, когда появляются эффективные методы ее обхода и обработки. Для работы с графами фундаментом служат два канонических алгоритма обхода: поиск в ширину (Breadth-First Search, BFS) и поиск в глубину (Depth-First Search, DFS). Понимание принципов их работы и математической сложности — абсолютный минимум для любого разработчика программного обеспечения.

Правильная раскраска графа — это такое назначение цветов его вершинам, при котором никакие две смежные вершины (соединенные ребром) не имеют одинакового цвета. Минимальное количество цветов, необходимое для такой раскраски, называется хроматическим числом графа. Эта, казалось бы, детская задача о раскрашивании картинок, в дискретной математике трансформировалась в мощнейший инструмент оптимизации ресурсов, планирования расписаний и проектирования компиляторов.

Планарный (плоский) граф — это граф, который можно нарисовать на плоскости таким образом, что его ребра будут пересекаться только в своих общих вершинах (узлах). Концепция планарности имеет колоссальное значение не только в чистой дискретной математике, но и в современной инженерии: именно эти законы определяют, можно ли развести дорожки на однослойной печатной плате без замыканий, или как оптимально спроектировать топологию микропроцессора.