I am trying to count the number of $4$-cycles in the hypercube $Q_n$. Clearly if $x,y$ are two distinct vertices with two common neighbors then we get a $4$-cycle. But how do I count such $x$ and $y$?
Thanks
I am trying to count the number of $4$-cycles in the hypercube $Q_n$. Clearly if $x,y$ are two distinct vertices with two common neighbors then we get a $4$-cycle. But how do I count such $x$ and $y$?
Thanks
I assume the vertex set $Q_n$ of your graph $G$ is the set $\{0,1\}^n\subset[0,1]^n$, $\ n\geq2$, and that the edges of $G$ connect any two vertices that differ in exactly one of their $n$ coordinates.
A four-cycle is an embedding $\phi$ of an "abstract square" $C_4:\ (0,0)\to(1,0)\to(1,1)\to(0,1)\to(0,0)$ into $G$. Up to orientation such an embedding is uniquely determined by the choice of the two coordinates that change along $\phi(C_4)$, and of the values of the $n-2$ coordinates that remain constant along $\phi(C_4)$. It follows that the total number $N_n$ of such cycles is given by $N_n={n\choose 2}\cdot 2^{n-2}\ .$ For $n=2$ and $n=3$ you get $N_2=1$ and $N_3=6$, as it should be.