Граф – это конечная совокупность вершин, некоторые из которых соединены ребрами.
Ребро не обязано соединять разные вершины. Если ребро соединяет вершину саму с собой, то такое ребро называют петлей.
Если две различные вершины графа соединены ребром, то такие вершины называются смежными.
Количество ребер, выходящих из одной вершины, называется степенью этой вершины.