I'm stumped on this one.
Let G be a forest containing 6 trees with 27 total vertices. What is the minimum number of simple paths for G?
I know how to compute this for an even number of vertices. For example, a forest with 4 trees and 18 total vertices would have at least 82 paths. You partition the total number of vertices:
$4^2 + 4^2 + 5^2 + 5^2 = 82 $
I'm not sure how to adapt this formula to an odd number of total vertices.
Best Answer
I don't see why it makes a difference if you have an odd number of vertices. You do exactly the same thing: divide the vertices up as evenly as possible.
You seem to already know this, but the total number of simple paths (counting a path and its reversal separately) in any tree with $k$ vertices is $k^2$. Every vertex is a path of length $0$, and for every pair of distinct vertices $(a,b)$ there is exactly one path from $a$ to $b$.
So if a forest has six trees with $k_1,...,k_6$ vertices respectively there are $k_1^2+\cdots+k_6^2$ paths, and you have to choose $k_1,...,k_6$ all positive with $k_1+\cdots+k_6=27$, to make $k_1^2+\cdots+k_6^2$ as small as possible. $27/6=4.5$, so this is achieved by taking three components of $4$ vertices and three of $5$, for $4^2+4^2+4^2+5^2+5^2+5^2=123$.