Longest simple walk in a complete graph
If $n$ is odd, the graph has an Euler trail, i.e., a simple walk on all $\tfrac12n(n-1)$ edges.  This is obviously optimal, since it uses every edge in the graph.

If $n$ is even, delete a matching of size $\tfrac12n-1$, i.e., delete a set of that many edges, no two of which share an endpoint. The resulting graph&nbsp;$G$ has two odd-degree vertices and $n-2$ even-degree vertices, so it has an Euler trail, which is a simple walk of length $$\tfrac12n(n-1) - (\tfrac12-1) = \tfrac12n(n-2)+1\,.$$ This is optimal. Any simple walk is an Euler trail of the graph formed from the vertices and edges of the walk. But any simple walk in $K_n$ longer than the one just described would have to contain at least four vertices of degree $n-1$, which is odd. And no graph with four odd-degree vertices has an Euler trail.