Связность, цепи, циклы и обход графа

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

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

Типичные ошибки: не считать одиночную вершину отдельной компонентой; считать вершины, а не рёбра при подсчёте степени; думать, что любую фигуру можно нарисовать «не отрывая карандаша».