 Common neighbourhood

The common neighbourhood of a vertex set $S$ in a simple graph is the intersection of the open graph neighbourhoods:Its vertices are adjacent to every member of $S$. This differs from the union-neighborhood convention $N(S)={\bigcup }_{v\in S}N(v)$, which asks for adjacency to at least one member. The notation must distinguish these two operations.

In the path $1-2-3$, vertices one and three have common neighbourhood $\{2\}$. In a triangle, the endpoints of an edge have the third vertex as their unique common neighbor. Neither endpoint belongs to the intersection, because a simple graph has no loops.

Common-neighbor counts detect triangles and other dense local patterns. In a bipartite graph with parts $A,B$, the common neighbourhood of a subset of $A$ lies in $B$ and identifies vertices simultaneously connected to the entire chosen subset.