Граф, вершина, ребро
Граф — это множество вершин и рёбер между ними. Вершина (узел) представляет объект, ребро — связь между двумя вершинами.

Здесь вершины A, B, C, D соединены рёбрами.

Представление задачи с помощью графа
Любую задачу с объектами и связями можно изобразить графом. Например, города (вершины) и дороги (рёбра).

Степень (валентность) вершины
Степень вершины — число рёбер, инцидентных ей. В приведённом графе степень вершины B =  (рёбра AB,BD).

Число рёбер и суммарная степень вершин
Если граф содержит E рёбер, то сумма степеней всех вершин равна 2·E.
Пример: в графе с 5 рёбрами суммарная степень = 10.

Цепь и цикл
Цепь — последовательность различных рёбер, соединяющих вершины.
Цикл — замкнутая цепь, возвращающаяся в исходную вершину.

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

Ориентированные графы
В ориентированном графе каждому ребру придаётся направление.