counting cycles in an undirected graph here is the problem:

this is the solution:

my question is this. how did they know that it has edges between all ${n \choose 2}$ pairs of nodes? also how did they know that there are $n \cdot (n-1) \cdot (n-2) \cdot  ...\cdot (n-p+1) $ sequences? (andy why exactly $(n-p+1)$) and why is each cycle counted $2p$ times? i guess im having trouble grasping the problem in whole. can someone please walk me through it?
 A: By definition $K_n$, the complete graph on $n$ nodes, has an edge between every pair of distinct nodes. Suppose that you want to construct a cycle of length $p$, where $3\le p\le n$. Pick any sequence of $p$ nodes, say $v_1,v_2,\ldots,v_p$; there’s an edge from $v_k$ to $v_{k+1}$ for $k=1,\ldots,p-1$, and there’s an edge from $v_p$ to $v_1$, so $v_1,v_2,\ldots,v_p,v_1$ is a cycle of length $p$. How many ways are there to pick such a sequence? We can choose any node to be $v_1$, so there are $n$ ways to choose $v_1$. The nodes $v_1,\ldots,v_p$ must all be distinct, so there are now $n-1$ possible choices for $v_2$. Once $v_1$ and $v_2$ have been chosen, there are $n-2$ nodes left from which to choose $v_3$. Continuing in this fashion, we see that after we’ve chosen $v_1,\ldots,v_{p-1}$, there are $$n-(p-1)=n-p+1$$ nodes left from which to choose $v_p$. Thus, there are altogether
$$n(n-1)(n-2)\ldots(n-p+1)\tag{1}$$
ways to choose a sequence of $p$ nodes. Note, however, that the $p$ cycles
$$\begin{align*}
&v_1,v_2,v_3,\ldots,v_p,v_1\\
&v_2,v_3,v_4,\ldots,v_p,v_1,v_2\\
&v_3,v_4,v_5,\ldots,v_p,v_1,v_2,v_3\\
&\;\vdots\\
&v_p,v_1,v_2,\ldots,v_{p-1},v_p
\end{align*}\tag{2}$$
are actually all the same cycle, just listed starting at a different point. Moreover, since we’re not distinguishing the direction of travel around a cycle, the $p$ cycles obtained by reversing each sequence in $(2)$ are also just different names for the same cycle. In other words, each cycle of length $p$ can be listed in $2p$ different ways, once for each combination of starting point and direction of travel. Formula $(1)$ counts the number of sequences of $p$ nodes, so it counts each cycle of length $p$ altogether $2p$ times, and therefore the number of distinct $p$-cycles is only
$$\frac{n(n-1)(n-2)\ldots(n-p+1)}{2p}\;.$$
When $p=n$ this becomes
$$\frac{n(n-1)(n-2)\ldots(n-n+1)}{2n}=\frac{n!}{2n}=\frac{n(n-1)!}{2n}=\frac{(n-1)!}2\;.$$

Here is an alternative argument that you may find a little simpler. Let $v$ be one of the nodes of $K_n$. A cycle of length $n$ will visit every node, so in particular it will visit $v$, and we might as well list it starting at $v$. We can visit the other $n-1$ nodes in any order, since there’s an edge between any two distinct nodes, and no matter where we end up, there’s an edge back to $v$ to complete the cycle. Since there are $(n-1)!$ permutations of the other $n-1$ nodes, this gives us $(n-1)!$ possible cycles of length $n$. However, that counts each cycle twice, once for each of the two directions in which we can traverse it, so the number of distinct undirected cycles of length $n$ is only half that, or 
$$\frac{(n-1)!}2\;.$$
For example, if $n=4$, and the nodes are labelled $1,2,3$, and $4$, the cycle $13421$ is the same as the cycle $12431$ obtained by traversing the nodes in the opposite direction. The problem really should have said explicitly that the cycles in question are undirected; if we were counting directed cycles, we’d count $13421$ and $12431$ as distinct, and we’d count a total of $(n-1)!$ cycles of length $n$ in $K_n$.
