= Common neighbourhood
{title2=$N_{\cap}(S)=\bigcap_{v\in S}N(v)$}
The common neighbourhood of a vertex set $S$ in a <simple graph> is the intersection of the open <graph neighbourhoods>:
$$
N_{\cap}(S)=\bigcap_{v\in S}N(v).
$$
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.
Back to article page
