# Moving an edge in a weighted tree to maximize longest path length

Let $G$ be a undirected edge-weighted tree, where all edge weights are positive. A move of an edge $\{u,v\} \in E(G)$ is the operation of deletion of $\{u,v\}$ and the addition of a new edge $\{x,y\}$, where $x,y \in V(G)$. Intuitively, we can think of the move meaning the deletion of an edge, and the re-insertion of it between two new vertices.

Now, given $G$, our task is to maximize the weight of a longest path in $G$ by a single move with the constraint that the newly obtained graph $G'$ remains a tree. An example is given below:

The longest path is E-B-C-D with weight 18 at the initial state. But if we move B-C to E-F we get a longest path A-B-E-F-C-D with weight 23.

One could rely on brute force, which is a feasible approach: remove an edge, try putting it between two vertices, check if a graph is still acyclic, find the longest path, try another pair of vertices, try another edge. You will end up with enumerating all possible acyclic graphs.

My question is the following: could we do better than brute-forcing all possibilities?

## 1 Answer

Hints:

When you remove an edge from the graph, you split it into two trees.

Given a tree, can you find the longest path in that tree? (It's not hard.)

Given two trees, can you find which edge to add to make the longest path in the resulting graph as long as possible? (Hint: first find the longest path in each of the two trees. Then..)

This is your exercise, so I'll let you take it from here. That should give you plenty to work with.