patternMinor
Longest simple walk in a complete graph
Viewed 0 times
simplegraphcompletewalklongest
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#45088, answer score: 5
Revisions (0)
No revisions yet.