6
$\begingroup$

A simple walk is a path that does not contain the same edge twice. A simple walk can contain circuits and can be a circuit itself. It just shouldn't have the same edge twice.

A simple undirected graph is an undirected graph with no loops and multiple edges. A complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A path of length $n$ is a sequence of n edges $e_1$,$e_2,\ldots,e_n$ such that $e_1$ is associated with $\{x_0,x_1\}$, $e_2$ with $\{x_1,x_2\},\ldots,e_n$ with $\{x_{n-1},x_n\}$.

What is the length of the longest simple walk in a complete graph with $n$ vertices?

What I tried: When $n$ is odd, every vertex has degree $n-1$ which is even. It follows that the graph has a euler circuit (every edge is included), therefore the longest walk length is $n(n-1)/2$, corresponding to the total number of edges.

But when $n$ is even, I try to follow similar reasoning and get stuck. I get a degree sequence, but I can't prove it is graphic. How could we handle the case where $n$ is even?

$\endgroup$
  • $\begingroup$ 1. Can you explain in what sense is this a computer science question? This sounds more like a pure mathematics question. Generally, we expect there should be some good reason a computer science perspective is useful or is most suitable to be answered by computer scientists, and we expect this context to be explained in the question. If you later decide this is more suitable for Math.SE, you can always flag it for moderator attention and ask them to migrate it. See meta.cs.stackexchange.com/q/704/755 and meta.cs.stackexchange.com/q/260/755. $\endgroup$ – D.W. Aug 8 '15 at 3:23
5
$\begingroup$

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 $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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.