Graph theory

Question

In tree for every pair of vertices u!=v in G their is exactly 1 path from u to v .Please help me to prove this

Comments

simply draw a tree on paper...  take any two vertices and name them as A and B

try to go from A to B.... how many paths you get? only one

right?

---

 Shivangi Parashar 2 just take a tree and try to go from one node to any other node , you will find it UNIQUE. Actually it is a theorem. If you want proof visit this http://www.cs.cmu.edu/afs/cs/academic/class/15251/Site/current/Materials/Handouts/lecture20-proofs.pdf

Answer 1

We can prove this by contradiction.

Let us assume that there exists more than one path from a vertex $i$ to vertex $j$.

If we take the union of these two paths, we will form a cycle, which contradicts the fact that we have a tree.

Hence, there can be only one unique path for every pair of vertices.

For more such proofs, see here: http://compalg.inf.elte.hu/~tony/Oktatas/TDK/FINAL/Chap%204.PDF

Comments

thats good approach