Discrete math Please write your answer neatly so that I can

Discrete math. Please write your answer neatly so that I can read it, thanks.

Prove that if there are two different paths between vertices x and y in a simple graph, then there must be a cycle in the graph.

Solution

Let xx and yy be vertices such that two distinct paths P1P1 and P2P2 join xx to yy such that P1P1 is of minimal length. (i.e. if two vertices xx, yy are connected by two paths then these paths must be at least as long as P1P1)

If P1P1 meets P2P2 at a vertex zz not equal to xx or yy then we obtain shorter paths P1P1 and P2P2 joining xx tozz, where P1P1 is shorter than P1P1 which is a contradiction.

Therefore, the path P1P2¯¯¯¯¯P1P2¯ (so follow P1P1, then P2P2 backwards), is a cycle in the graph