Let n ≥ 8. Give a big-Θ estimate for the number of circuits of length 8 in Kn. Θ(n) Θ(n8) Θ(8) Θ(8n) Θ(8n)

ddaeeric

ddaeeric

Answered question

2021-06-23

Let n8. Give a bigΘ estimate for the number of circuits of length 8 in Kn. Θ(n)Θ(n8)Θ(8)Θ(8n)Θ(8n)

Answer & Explanation

hesgidiauE

hesgidiauE

Skilled2021-06-24Added 106 answers

A complete graph Kn(n1) is a simple graph with n vertices and an edge between every pair of vertices.
Definition permutation (order is important): nPr=n!nr!
Definition combination (order is not important)| nCr=(nr)=n!r!(nr)! with nn(n1)21
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 n8, 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. nPs=n!n8n(n1)(n2)(n7)
Every circuit will be counted twice in the n(n1)(n2)(n7) sequences, as the opposite order of the sequence of vertices will lead to the same vertex, thus there are n(n1)(n2)n72 circuits of length 8.
Since n(n1)(n2)(n7) is a polynominal function of degree 8, n(n1)(n2)(n7)isΘ(n8)

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?