Common neighborhood property

62 Views Asked by At

First of all, I will introduce some notations: $N(v)$ denotes the neighbourhood of a vertex $v$ in a graph and $e(B,C)$ denotes the number of orderes pairs $(b,c)$, where $b \in B$, $c \in C$ and and $bc$ is an edge on $G$. Let $X$ be an unspecified subset of vertices and $Y$ be the set of all neighbors of $v$ in $G$.

I cannot understand the following \begin{equation} \sum_{u\in X}|N(u) \cap N(v)| = e(X,Y). \end{equation}

My problem is, that $X \neq N(u)$. Can somebody help me?

1

There are 1 best solutions below

2
On

$s(X,Y)$ counts the number of edges between all elements $u$ of $X$ and all elements of $Y=N(v)$, which is exactly the same as counting the number of elements in $N(v)$ that are connected to a specific $u \in X$ and then summing over all $u \in X$, which is exactly what your sum does.