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 path 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 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 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 path 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 path 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 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 path 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?

What is the length of the longest simple path in a complete graph with n veritces?

Terminology :

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$...,e$_n$ such that e$_1$ is associated with {x$_0$,x$_1$}, e$_2$ with {x$_1$,x$_2$},... e$_n$ with {x$_{n-1}$,x$_n$}.

A simple path is a path that does not contain the same edge once.

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 path 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 path 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?