Connectedness in undirected graphs
An undirected graph is called connected iff there is a path between
every pair of distinct vertices in the graph.
Theorem 1: There is a simple path between every pair of vertices of
a connected undirected graph.
Proof: Assume e1,…,en is a shortest path from v to u.
If this path is not simple, then we should have ei=ej for some 1<i<j<n.
But observe that then if we delete ei+1,…,ej, we still have a path from
v to u, and this path is shorter than the original one.
Thus, a shortest path (which always exists) is simple. EOP