Consider an undirected graph G=(V,E)G=(V,E) where every edge e has a given cost C_e. Assume that all edge costs are positive and distinct. Let T be a minimum spanning tree of G and P be a shortest path from the vertex s to the vertex t. Now suppose that the cost of every edge of G is increased by 1 (for each edge: C_e=C_e+1). Call this new graph G.

Is T a minimum spanning tree of G? Is P the shortest s-t path of G?

Consider an undirected graph G (V, E) where every edge e has a given cost ce Assume that all edge costs are positive and distinct. Let T be a minimum spanning tree of G and P be a shortest path from the vertex s to the vertext. Now suppose that the cost of every edge of G is increased by 1 (for each edge: ce ce 1). Call this new graph G Is T a minimum spanning tree of G'? Is Pthe shortest s-t path of G