Question

Proof by contradiction.

Suppose we know the shortest path from A to D is A to B to C to D. Using the technique of proof by contradiction, show why the shortest path from A to C must be A to B to C.

Answer 1

See proof below

Explanation:

For the sake of finding a contradiction, suppose that the shortest path from A to C is not A-B-C. Then, the shortest path from A to C does not cross the point B, that is, there exist some point P≠B such that A-P-C is the shortest path from A to C.

Now, consider the path A-P-C-D from A to D. This path is shortest than the path A-B-C-D, because A-P-C is shorter than A-B-C and the remaining part of both paths, C-D, contributes the same length.

More specifically, call X the length of the path A-B-C, Y to the length of the path A-P-C and Z to the lenegth of the path C-D. Then Y<X, hence Y+Z<X+Z, but Y+Z is the length of the path A-P-C-D and X+Z is the length of the path A-B-C-D.

We have found a path (A-P-B-D) from A to D shortest than the shorter path from A to D, which is a contradiction. Therefore, our assumption that the shortest path from A to C is not A-B-C must be false, which implies that the shortest path from A to C must be A to B to C.