Most vital arc problem. A vital arc of a network is an arc whose removal from the

network causes the shortest distance between two specified nodes, say node s and node

t, to increase. A most vital arc is a vital arc whose removal yields the greatest increase

in the shortest distance from node s to node t. Assume that the network is directed,

arc lengths are positive, and some arc is vital. Prove that the following statements are

true or show through counterexamples that they are false.

(a) A most vital arc is an arc with the maximum value of Cij.

(b) A most vital arc is an arc with the maximum value of cij on some shortest path

from node s to node t.

(c) An arc that does not belong to any shortest path from node s to node t cannot be

a most vital arc.

(d) A network might contain several most vital arcs.