Minimal edge-covering path in complete graph

534 Views Asked by At

Let $K_n$ be the complete graph with $n$ vertices. An edge-covering path in $K_n$ is a path going through every edge of $K_n$. The length of an edge-covering path is the number of edges (with multiplicity) in the path.

I am looking for the minimal length $L_n$ of an edge-covering path in $K_n$ for all $n$.

If $n$ is odd, then $K_n$ is an Eulerian graph. Hence $L_n = n(n-1)/2$.

What is the value of $L_n$ when $n$ is even? I find $L_2=1$, $L_4= 7$ and $L_6=17$. My guess would be $L_n = n(n+3)/2$ when $n\geq 4$ is even.

1

There are 1 best solutions below

0
On

Euler Theorem for multigraphs easily implies that the minimal length of an edge-covering path in a graph $G$ with possible multiple edges is the number $e(G)$ of edges of $G$ plus the minimal number of edges we have to add to $G$ to make it connected with all or all but two vertices have even degree. In particular, for $K_n$ with even $n$ we make $n-2$ vertices to have an even degree, which can be done by adding exactly $(n-2)/2$ edges. Thus $$L_{n}=e(K_n)+ (n-2)/2=n(n-1)/2+(n-2)/2=n^2/2-1.$$