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

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

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

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