Пусть V – некоторое непустое множество ( 
).
– множество всех его двухэлементных подмножеств, 
– неупорядоченная пара элементов множества 
. 
.
Неориентированный граф G – пара множеств (V,E), 
, где
V – множество вершин графа G,
E – множестворёбер графа G.
Если |V|=p, а |E|=q, то обозначают граф G,как (p,q)-граф или p-граф.
Смежные вершины графа G– вершины, соединенные ребром.
Смежные ребра графа G– ребра, имеющие общую вершину.
Инцидентные ребро и вершина – вершина является одним из концов ребра.
Конечный граф – множество вершин графа конечно.
