The graph neighborhood of a graph vertex is terminology whose convention must be specified. The open graph neighborhood
consists of the vertices adjacent to
, excluding
itself. The closed neighborhood
also includes
. Some sources use "graph neighborhood" specifically
for
, while others use "neighborhood" for
.
More generally, the th
neighborhood of
is the set of all vertices at graph distance
from
.
The subgraph induced by the neighborhood of a graph from vertex
is called the neighborhood graph.
The term "graph neighbors" generally means vertices adjacent to excluding
itself (Brouwer et al. 1989).
For a simple graph on
vertices with average vertex
degree
, where
, and any integer
, there are
distinct vertices
,
,
whose open neighborhoods
satisfy
This bound is asymptotically sharp for fixed and
. The two terms arise
from random graphs
and from a complete graph
on about
vertices together with isolated
vertices, respectively (Pach 2026).