Given 

- a simple, symmetric, weighted graph $G(V,E,W); \text{card}(V)=n,\ \text{card}(E)=m\le\frac{n(n-1)}{2} $ 
- a set of ordered pairs of vertices $U=\lbrace (u_i,u_j)\rbrace\subset V\times V,\ i\lt j$  
- a permutation of $\pi(E)$ that resembles an ordering of the edges 
 
<br>
>**Question:**  

>how fast can the appearance of a path between *any* $(u_i,u_j)\in U$ be detected, if the edges of $G$ are inserted one by one in the order defined by $\pi(E)$ into a graph $H$, that initially only contains the set $V$ of vertices of $G$?  

<br>

Answers stating the conditions, under which a specific algorithm will be fast(est) would be a great help in testing a (probably new) TSP heuristic.