319 views
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

1 Answer

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

edited by

Related questions

1 votes
1 votes
1 answer
1
0 votes
0 votes
1 answer
2
gagan55 asked Jun 30, 2023
177 views
Number of hamiltonian cycles for a graph K 5, 5( bipartite graph ) ??
0 votes
0 votes
1 answer
3
Dhiraj_777 asked May 4, 2023
488 views
In a Connected Planar Bipartite Graph of order 10 atmost how many edges be present ?
0 votes
0 votes
1 answer
4
Sahil_Lather asked Apr 15, 2023
439 views
Graph G is obtained by adding vertex s to $K_{3,4}$ and making s adjacent to every vertex of $K_{3,4}$ .The find the minimum number of colours required ot edge-colour is ...