Граф, или неориентированный граф  — это упорядоченная пара , где  — это непустоемножество вершин или узлов, а  — множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.

 (а значит и, , иначе оно было бы мультимножеством) обычно считаются конечными множествами. Многие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) длябесконечных графов, поскольку не все утверждения, имеющие место для конечных совокупностей, выполняются в случае бесконечных множеств.

Вершины и рёбра графа называются также элементами графа, число вершин в графе  — порядком, число рёбер  —размером графа.

Вершины  и  называются концевыми вершинами (или просто концами) ребра . Ребро, в свою очередь,соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину.

Два ребра называются кратными, если множества их концевых вершин совпадают.

Ребро называется петлёй, если его концы совпадают, то есть .

Степенью  вершины  называют количество инцидентных ей рёбер (при этом петли считают дважды).

Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.