The tutor considers a problem from Grimaldi about max trail length on K_n.

For a briefing about the complete graph K_n, check my post from yesterday.

In graph theory, a trail is a route that doesn’t repeat any edges. Unlike a circuit, a trail is not expected to return to its start vertex.

Grimaldi poses the question on page 558: What is the maximum trail length on K₆, then on K_2n?

Solution:

For K₆, we know it has six vertices. Furthermore, each vertex has degree 5, and is joined to all the others. To reach a vertex and leave it again uses two of its edges, so any vertex between the first and last can have only an even number of its edges used. However, the beginning vertex will have an odd number of edges used in the trail, since starting only uses one edge. (The end vertex, for a similar reason, will have an odd number of its edges used.)

Since each edge is connected to all the others, “stranding” won’t be a problem. Therefore, the trail can use four of the five edges of each of its four “inner” vertices, and all five of its first and last: 4×4 + 2×5=26. However, each edge is counted twice: once for each vertex it touches. Therefore, the length of the trail is 26/2 = 13 edges. On K₆, the maximum trail length is 13 edges.

K_2n, of course, has 2n vertices. Each vertex joins to 2n-1 edges. On the trail, there are 2n-2 vertices between the first and last. Therefore, its max trail length is

[(2n-2)(2n-2) + 2(2n-1)]/2

which becomes

[4n²-8n +4 +4n – 2]/2

then simplifies to

[4n²-4n + 2]/2

and finally

2n²-2n + 1

The complete graph K_2n has maximum trail length 2n² – 2n + 1 edges.

Source:

Grimaldi, Ralph P. Discrete and Combinatorial Mathematics. Don Mills: Addison-
  Wesley, 1994.

Jack of Oracle Tutoring by Jack and Diane, Campbell River, BC.