Prove Shortest Path Graph N Nodes Cannot Longer N 1 Arcs Q37021049

December 8, 2021 by Administrator

Prove that the shortest path in a graph with n nodes cannot belonger than n-1 arcs.

Answer

STATEMENT TO BEPROVED =>

Prove that the shortest path in a graph with n nodes cannot belonger than n-1 arcs.

PROOF=>

The shortest path in a graph with n nodes cannot be longer thann-1 arcs, means that, a graph with n nodes has at least n-1edges.

Now, I am going to prove this with the help of induction.

Let us suppose that there is a graph G with n nodes and e edges.According to the statement to be proved, e should be equal to n-1.—-(1)

Now, let us