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.
On
From the example you give one is lead to the conjecture that the total number of paths in a tree with $j$ vertices is minimal when the tree is a path graph of length $j-1$. The number of (directed) subpaths then is $j^2$. Assuming this it seems that the total number of paths in a forest is minimal if the all trees in this forest are path graphs, and have about the same size.
Im not going into the proof of the first of these conjectures (if true). For the second it suffices to consider two path graphs $\Gamma$ and $\Gamma'$ with $j$ and $j'$ vertices, and to show that, if $j'\geq j+2$ you can make the total number of subpaths smaller by making $\Gamma$ one edge longer and $\Gamma'$ one edge shorter.
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$.