We explore a problem to do with counting the number of paths of a certain length in a tree, in relation to the tree's number of vertices, and its diameter. In particular, for a tree with n vertices, we find conditions under which the number of paths of length k is at least n - k (the number of paths of length k for a linear tree, i.e. a straight line, with n vertices).
00:00 Intro
00:11 Terminology
00:53 Counting paths: linear tree
02:30 Posing the problem
03:11 Intuition through examples
05:54 Constructing paths of length k
08:13 Worst case scenario bound
10:10 Is our bound optimal?
13:26 Conclusion
