A trail is a sequence of adjacent vertices with no repeated edges. A circuit is a trail that begins and ends at the same vertex. The complete graph on 3 vertices has a circuit of length 3. The complete graph on 4 vertices has a circuit of length 4. the complete graph on 5 vertices has a circuit of length 10.
How can I find the maximum circuit length for the complete graph on n vertices?
Best Answer
This question is highly related to Eulerian Circuits.
Definition: An Eulerian circuit is a circuit which uses every edge in the graph.
By a theorem of Euler, there exists an Eulerian circuit if and only if each vertex has even degree. Hence, the maximum circuit length for $n$ vertices is $\frac{n(n-1)}{2}$ when $n$ is odd (the total number of edges), and $\frac{n(n-1)}{2}-\frac{n}{2}=\frac{n(n-2)}{2}$ when $n$ is even (we can just delete one edge for each two vertices to make the degree of every vertex even).