Prove that a graph G is a tree if and only if for every pair

Prove that a graph G is a tree if and only if for every pair of vertices u, v,
there is exactly one path from u to v.

Solution

G is a graph, in which for every pair of vertices u,v, there is a unique path from u to v.

To prove: G is a tree.

For this, we have to prove:

1. G is connected

and

2. G has no cycle.

Proof of 1: Since for every pair of vertices u and v, there is a path from u to v and (1) is proved.

Proof of 2:

Suppose there is a cycle in G with vertices v₁, v₂,.., v_k and edges v₁v₂, v₂v₃,..., v_kv₁.

Then, there are two paths between v₁ and v_k: viz., v₁, v_k and v₁,v₂,..., v_k. This is a contradiction to the statement that between every two vertices there is a unique path connecting them. So, G contains no cycles.

This provesthe theorem.