Problem Detail: 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?
Asked By : atulgangwar
Answered By : David Richerby
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/45088 Ask a Question Download Related Notes/Documents
