Prove that if a path exists between two vertices $u$ and $v$ in a directed or undirected graph, a simple path exists between $u$ and $v$.

Question

I got started on this proof, but I'm not so great at proofs, so I'm wondering how to finish this.

Given graph $G$ has nodes $V = \{v_1,v_2,v_3, \ldots\}$ where $u \in V$ and $v \in V$, suppose path $P$ has the form $\{u,\ldots,v\}$ where $u$ is the start and $v$ is the end. Any repeated vertex means the path is not simple by definition.

I'm not sure where to go from here in the proof. This proof is obvious, but it's hard for me to put in mathematical terms.

Thanks

Answer 1

if you look for kind of a formal proof, then you can try something like that: let $P$ be the path between $u$ to $v$, as $u,v\in V$, and P has the form $\{u,...,v\}$. if P is simple then we finish, otherwise, there is a sequence in P s.t $\{v_i,...,v_i\}$ for some $v_i \in V$ (there is a cycle that start and finish in $v_i$. we can look at $P'$ as the sequence in P until the first $v_i$, concatenated with the sequence in P from the second $v_i$.we shall do this for every cycle in P, and we shall get P' a path that is simple, because it is still a path (we passed through a valid edges), and we don't have any repeated node.