A graph is a tree iff any 2 vertices are connected by a unique path (Proof Verification)

1.5k Views Asked by At

Suppose $T$ is a tree and $u,v$ are vertices s.t there are 2 distinct paths between them.

i.e. $u,u_1,u_2,...,u_n, v$ and $u,u'_1,u'_2,...,u'_m, v$.

If $\forall u_i$, $u_i\notin \{u'_1,u'_2,...,u'_m\}$ this implies $u,u_1,..,v,u'_m,..,u$ is a cycle in T. Contradiction

If not let $I$ be the least index s.t $u_i\in \{u'_1,u'_2,...,u'_m\}$.

Therefore, $u,u_1,u_2,...,u_I,u'_{I-1},u'_{I-2},...,u$ is now a cycle in T. Contradiction.

Hence, there is a unique path between any 2 vertices.

For the other direction suppose for contradiction there is a cycle in T i.e. $u,u_1,u_2,...,u_n,u$. Then, $u,u_1$ and $u,u_n,u_{n-1},..,u_1$ are 2 distinct paths in T.

Are the above proofs correct?

1

There are 1 best solutions below

2
On

Nearly. Remember that a tree is both acyclic and connected. You showed that a graph with a cycle contains two vertices that are not connected by a unique path, but you also need to show that a disconnected graph also contains two vertices that are not connected by a unique path.