 Let n ≥ 8. Give a big-Θ estimate for the number of circuits of length 8 in Kn. Θ(n) Θ(n8) Θ(8) Θ(8n) Θ(8n) ddaeeric 2021-06-23 Answered
Let $$\displaystyle{n}≥{8}$$. Give a $$\displaystyle{b}{i}{g}-Θ$$ estimate for the number of circuits of length 8 in Kn. $$\displaystyleΘ{\left({n}\right)}Θ{\left({n}{8}\right)}Θ{\left({8}\right)}Θ{\left({8}{n}\right)}Θ{\left({8}{n}\right)}$$

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it hesgidiauE

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)}$$