Questions about proving some claims. Doesnt have to be specific proofs. Just general statement proving the claims should work.

Critical Edges question. Just proofs and claims. 2. (15 points) Critical Edges You are given a graph G = (V, E) a weight function w : E R, and a source vertex s. Assume w(e0 for all e E E We say that an edge e is upwards critical if by increasing) by any e>0 we increase the shortest path distance from s to some vertex vE V. We say that an edge e is downwards critical if by decreasing w(e) by anye0 we decrease the shortest path distance from s to some vertex v E V (however, by definition, if w(e) 0then e is not downwards critical, because we can't decrease its weight below a) (5 points) Claim: an edge (u,is downwards critical if and only if there is a shortest path from s to v that ends at (u, v), and w(u, v)>0. Prove the claim above. b) (5 points) Make a claim similar to the one above, but for upwards critical edges and prove it (c) (5 points) Using the claims from the previous two parts, give an O(E log V) time algorithm that finds all downwards critical edges and all upwards critical edges in G