В теории графов смежной вершиной вершины v называется вершина, соединённая с v ребром. Окрестностью вершины v в графе G называется порождённый подграф графа G, состоящий из всех вершин, сопряжённых v и всех рёбер, соединяющих две такие вершины. Например, рисунок показывает граф с 6 вершинами и 7 рёбрами. Вершина 5 смежна вершинам 1, 2 и 4, но не смежна вершинам 3 и 6. Окрестность вершины 5 — это граф с тремя вершинами 1, 2 и 4, и одним ребром, соединяющим вершины 1 и 2.
Окрестность часто обозначается как NG(v) или (если известно, о каком графе идёт речь) N(v). То же самое обозначение окрестности может использоваться для ссылки на множество смежных вершин, а не на соответствующий порождённый подграф. Окрестность, описанная выше, не включает саму вершину v и об этой окрестности говорят как об открытой окрестности вершины v. Можно определить окрестность, включающую v. В этом случае окрестность называется закрытой и обозначается как NG[v]. Если не указано явно, окрестность предполагается открытой.
Окрестности можно использовать для представления графов в компьютерных алгоритмах через список смежности и матрицу смежности. Окрестности используются также в коэффициенте кластеризации[англ.] графа, который измеряет среднюю плотность его окрестностей. Вдобавок, много важных классов графов можно определить свойствами его окрестностей или взаимной симметрией окрестностей.
Изолированная вершина не имеет смежных вершин. Степень вершины равна числу смежных вершин. Специальным случаем является петля, соединяющая вершину с той же самой вершиной. Если такое ребро существует, вершина принадлежит собственной окрестности.
Если все вершины графа G имеют окрестности, изоморфные некоторому графу H, говорят, что G является локально графом H, и если все вершины G имеют окрестности, принадлежащие некоторому семейству графов F, говорят, что G является локально графом F[1][2]. Например, в графе октаэдра, показанном на рисунке, каждая вершина имеет окрестность, изоморфную циклу из четырёх вершин, так что октаэдр является локально C4.
Для множества A вершин, окрестность A — это объединение окрестностей вершин, так что она содержит все вершины, сопряжённые с, по крайней мере, одним членом A.