Number of distinct path in a graph with $n$ vertices

$\begingroup$

Let $T = (V , E)$ be a tree with $|V | = n\geqslant 2$. How many distinct paths are there (as sub graphs) in $T$?

I already have the answer to this question as $(n/2)$. The problem that I'm having is finding anything in the text that helps me to figure out how to arrive at this answer.

$\endgroup$

1 Answer

$\begingroup$

Any two vertices of a tree are connected by a unique path, so there are exactly $\dbinom n2$ paths of length at least one. If you also count one-point paths (why wouldn't you?) there are $n$ of those, making a total of $\dbinom n2+\dbinom n1=\dbinom{n+1}2=\dfrac{n(n+1)}2$ paths in a tree $T=(V,E)$ with $|V|\ge1$.

$\endgroup$ 0

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy