0 votes 0 votes 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 Shivangi Parashar 2 asked Aug 17, 2018 Shivangi Parashar 2 319 views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Shaik Masthan commented Aug 17, 2018 reply Follow Share 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? 1 votes 1 votes Rishav Kumar Singh commented Aug 17, 2018 reply Follow Share 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 1 votes 1 votes Please log in or register to add a comment.
1 votes 1 votes 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 goxul answered Aug 17, 2018 edited Aug 17, 2018 by goxul goxul comment Share Follow See 1 comment See all 1 1 comment reply Rishav Kumar Singh commented Aug 17, 2018 reply Follow Share thats good approach 0 votes 0 votes Please log in or register to add a comment.