Travelling through all edges in a complete graph I have a complete graph with 14 vertices (all edges have equal weight). What is the shortest way to go through all edges?
Edit: I've got a lower bound:  as I go through every edge, I visit every vertex at least $\left\lceil\frac{13}2\right\rceil$ times so the path contains at least 98 vertices. But don't know if such way exists.
 A: First of all, note that $K_{14}$ itself contains 91 edges, but has all its vertices of odd degree, so does not immediately have an Eulerian path or cycle.
To make the graph have an Eulerian path, we need to add edges such that at most two vertices have odd degree. Only six edges are necessary: labelling the vertices $V_1$ to $V_{14}$, insert the edges $V_1V_2$, $V_3V_4$ and so on until $V_{11}V_{12}$. Hence if you don't mind ending at a different place from where you started, 97 edges suffice – the path endpoints are $V_{13}$ and $V_{14}$.
If you want an Eulerian circuit that takes you back to your starting point, you do need the $V_{13}V_{14}$ edge, leading to your lower bound of 98 edges.
In both cases, if an Eulerian path or circuit should exist in the graph from degree considerations and the graph is connected (which it is), then it can be explicitly constructed. Hence the shortest path in $K_{14}$ using all edges has 97 edges, while the shortest circuit has 98.
A: A complete graph with 14 vertices has $\frac{14(13)}{2}$ edges. This is 91 edges.
However, for every traversal through a vertex on a path requires an in-going and an out-going edge. Thus, with an odd degree for a vertex, the number of times you must visit a vertex is the degree of the vertex divided by 2 using ceiling division (round up).
With a complete graph of 14 vertices, each vertex is degree 13. Each vertex thus has 6 in-out pairs and an odd edge. Therefore, an algorithm must pass through the vertex 7 times, and thus traverse 14 edges per vertex, with one of the 13 unique edges traversed twice.
Note that if the path is not required to be a cycle, we can have the start and end vertices be unique. Therefore, if we assume that we traverse the graph through only the in-out pairs, we will be left with the end-point of this path (call it $A$) such that we have traveled $6*14 = 84$ edges.
Note that there are 14 degree-edges (or directional edges) still remaining. We can pair these edges off to the remaining vertices such that, given that we consider the set of vertices in the graph to be well-ordered and mappable to the positive integers starting from 1 ascending, each even numbered vertex will be paired up with an odd numbered vertex. There are thus 2 sides for each undirected edge, and thus only 7 undirected edges we will uniquely traverse. Thus, our count goes up to $84 + 7 = 91$ edges.
However, note that we are left with 7 unique subgraphs graphs with respect to only unique, still un-traversed vertices (the edges which connect two vertices that we just established) which are not connected. Since we have already traversed all other edges, we are sure that these are all mutually unconnected outside of their individual networks. Thus, if we consider these networks as "supervertices" such that we can abstract each network as a vertex, we want to create a path between the vertex by inserting edges as needed. To make a path between $n$ unconnected vertices, $n-1$ vertices must be inserted. Since there are 7 "supervetices" or unconnected subgraphs, we insert or re-traverse 6 more vertices.
Our total traversal count is thus $6 + 91 = 97$ edges. Once again, if we were to reconnect ourselves back to the original vertex, we would need to insert a vertex between the first and last supervertex/subgraph such that the actual connecting vertices is the first in our path and the end in the non-cyclic path that has $97$ edges to $97 + 1 = 98$ vertices. Hence, the optimal path has 98 vertices.
