graph theory
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.
I am not sure if there is a way to assign weights to nodes. Perhaps you can replace each node by an edge with negative weight according to its desirability. Also you can have positive weights on the rest of the edges as usual. Now the problem reduces to the known problem of finding shortest path (least total weight). Algorithms such as Dijkstra or Floyd–Warshall algorithm can solve this efficiently. https://en.wikipedia.org/wiki/Shortest_path_problem
I'll lay out an approach / hint in the first part, and then complete the proof in the second part of the post.
We can assume $k>1$. If $G$ has a vertex of degree $k$, we are done. So we assume that the maximum degree of $G$ is some $\Delta \leq k-1$.
We let $u$ be a vertex of $G$, and assume for the sake of contradiction that $G$ does not contain any path of length $k$. In particular, this means that the diameter of $G$ is at most $k-1$ (since $G$ is connected and has no $k$-path), so every vertex of $G$ is within distance $k-1$ of $u$ (this is where connectivity is useful!).
If you just wanted a hint / way to approach the problem, stop reading here.
Now given the degree and distance constraints we have so far, let's see how many vertices $G$ can have. We introduce the notation:
$$N_i(u) = \{v\in G : d(u,v) = i\}$$ The vertex $u$ has at most $(k-1)$ neighbours at distance $1$ from it (i.e., we have $|N_1(u)| \leq k-1$). Each of these in turn has at most $(k-2)$ neighbours besides $u$. So the set $N_2(u)$ of vertices distance $2$ from $u$ has $|N_2(u)| \leq (k-1)(k-2)$ (see the diagram).
In general, we get that $|N_i(u)| \leq (k-1)(k-2)^{i-1}$. So the total number of vertices $n$ is bounded above as follows:
$$n = |\{u\}| + |N_1(u)| + \dots + |N_{k-1}(u)|$$
And thus:
$$n \leq 1 + (k-1) + (k-1)(k-2) + \dots + (k-1)(k-2)^{k-2} = 1 + (k-1)\sum_{i=0}^{k-2}(k-2)^i$$
By using the formula for the sum of a geometric series, and a bit of inequality juggling, you can show that $n \leq k^k$. Thus the total possible number of edges that $G$ has is at most $\binom{n}{2} \leq \binom{k^k}{2}$. But this yields a contradiction, so $G$ must have a $k$-path.
Best Answer
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.