Graphs containing all trees on 
vertices as subgraphs were investigated
by Chung and Graham (1978) and Chung et al. (1976). In this work, the term
"fully 
-forested
graph" is adopted for a graph that contains all trees
on 
vertices. A "smallest fully 
-forested graph" is then a fully 
-forested graph with the smallest possible number of edges
for a given 
.
(Note that, confusingly, Chung and Graham (1978) in general use 
to refer to the number of vertices in a graph, but in the
context of trees 
,
their paper uses 
to refer to the number of edges.)
For example, there are six trees on 6 vertices, as illustrated in the top row above. The graph in the bottom row is fully 6-forested because it contains each of these 6 trees as a subgraph.
The least numbers of edges in a smallest fully 
-forested graph for 
, 2, ... are 0, 1, 2, 4, 6, 8, 11, 13, 16, 18, ... (OEIS
A004401). The first eight of these values were
given by Chung and Graham (1978, Table I).
By its definition, a fully 
-forested graph must have the path
graph 
as a subgraph and therefore must itself contain at least
vertices. For 
, an optimal host with exactly 
vertices is known. Whether
such a host always exists is open (Chung and Graham 1978). If so, the smallest numbers
of edges for 
and 12 are 22 and 24.
An optimal host need not have exactly 
vertices. For example, subdividing one graph
edge of the 4-vertex star graph gives a 5-vertex,
4-edge host containing both 4-vertex trees.
Among hosts with exactly 
vertices, all smallest fully
-forested
graphs up to (at least) 
are also planar and traceable.
In addition, a fully 
-forested graph must have a graph
vertex of degree at least 
. Together with the fact that it must contain 
as a subgraph, this forces
an edge count of 
(Chung and Graham 1978).
The graphic above shows all smallest fully 
-forested graphs on exactly 
vertices for 
to 7. Compare with Fig. 3 in Chung and Graham (1978),
whose 
(corresponding to 3 edges = 4 vertices) is erroneous since it does not contain the
path graph 
and has 3 (but should have 4) edges.
The numbers of smallest fully 
-forested graphs on exactly 
vertices for 
, 2, ... are 1, 1, 1, 1, 2, 2, 7, 13, 25, 17, ... (OEIS A380740).
