- For other meanings of neighbourhoods in mathematics, see Neighbourhood (mathematics). For non-mathematical neighbourhoods, see Neighbourhood (disambiguation).
In
graph theory, an
adjacent vertex of a
vertex v in a
graph is a vertex that is connected to
v by an
edge. The
neighbourhood of a vertex
v in a graph
G is the induced subgraph of
G consisting of all vertices adjacent to
v. For example, the image shows a graph of 6 vertices and 7 edges. Vertex 5 is adjacent to vertices 1, 2, and 4 but it is not adjacent to 3 and 6. The neighbourhood of vertex 5 is the graph with three vertices, 1, 2, and 4, and one edge connecting vertices 1 and 2.