A complete graph \(\displaystyle{K}{n}{\left({n}\Rightarrow{1}\right)}\) is a simple graph with n vertices and an edge between every pair of vertices.

Definition permutation (order is important): \(\displaystyle{n}{P}{r}={n}\frac{!}{{{n}-{r}}}!\)

Definition combination (order is not important)| \(\displaystyle{n}{C}{r}={\left({n}{r}\right)}={n}\frac{!}{{{r}!{\left({n}-{r}\right)}!}}\) with \(\displaystyle{n}\ne{n}\cdot{\left({n}-{1}\right)}\cdot\ldots\cdot{2}\cdot{1}\)

Solution Let n be the number of vertices in Kn

When \(n<8\), the graph contains less than 8 vertices and thus the graph can then not contain a circuit of length 8. 0 circuits of length 8 when \(n<8\)

When \(\displaystyle{n}\Rightarrow{8}\), any circuit of length 8 is a sequence of 8 vertices (as the last vertex in the sequence will be the first circuit again). The order of the vertices matters (as a different order will lead to the same sequence), thus we use the definition of a permutation. \(\displaystyle{n}{P}{s}={n}\frac{!}{{{n}-{8}}}\ne{n}{\left({n}-{1}\right)}{\left({n}-{2}\right)}\ldots{\left({n}-{7}\right)}\)

Every circuit will be counted twice in the \(n(n-1)(n-2)\cdots(n-7)\) sequences, as the opposite order of the sequence of vertices will lead to the same vertex, thus there are \(\displaystyle{n}{\left({n}-{1}\right)}{\left({n}-{2}\right)}\ldots\frac{{{n}-{7}}}{{2}}\) circuits of length 8.

Since \(n(n-1)(n-2)\cdots(n-7)\) is a polynominal function of degree 8, \(\displaystyle{n}{\left({n}-{1}\right)}{\left({n}-{2}\right)}\ldots{\left({n}-{7}\right)}{i}{s}Θ{\left({n}^{{8}}\right)}\)