Граф G=(V,E) - совокупность не пустого множества вершин V и множества его двух элементарных подмножеств ребер E
Между элементами множества вершин и множества ребер определено отношение инцидентности. Говорят, что ребро е инцидентно вершинам v, w, если оно соединяет эти вершины и наоборот, каждая из вершин v, w инцидентна ребру е.
Две вершины называются смежными, если существует ребро, концами которого они являются. Два ребра называются смежными, если они имеют общую вершину.
Окрестность вершины - множество смежных с ней вершин.
Степенью вершины v графа G называется число d(v) ребер графа, которым инцидентна эта вершина.