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

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

Для объективной оценки эффективности алгоритмов инженерам и математикам необходим строгий аппарат, позволяющий сравнивать скорость работы программы или объем потребляемой памяти независимо от тактовой частоты конкретного процессора, архитектуры компьютера или используемого языка программирования. В дискретной математике эту фундаментальную задачу решает асимптотический анализ и знаменитая нотация О-большое (Big O).