Граф G как математический объект - это совокупность двух множеств: непустого множества вершин V и множества ребер E, элементы которого представляет собой неупорядоченные (для ориентированного графа - упорядоченные) пары элементов из множества V.
G(V,E) = < V; E >, n(V) > 0, E c V x V
для неориентированного графа E = E^(-1) (бинарное отношение Е - симметрично).
Минимальный граф состоит из одной вершины.
Каждому неориетированному графу можно поставить в соответствие ориентированный граф, в котором каждое ребро заменено двумя противоположно ориентированными ребрами, инцидентными тем же вершинам.
Пусть v1 и v2 - вершины, e = (v1,v2) - соединяющее их ребро.
Тогда вершина v1 и ребро e инцидентны, вершина v2 и ребро e также инцидентны. Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.
Обычно граф изображают в виде диаграммы: вершины - точками, ребра - линиями, соединяющими инцидентные вершины.