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. While all smallest 
-forested graphs up to at least 
contain exactly 
vertices, it is not known if this is always the case (Chung
and Graham 1978). If is true, then the smallest numbers of edges for 
and 12 are 22 and 24.
All smallest fully 
-forested
graphs up to (at least) 
are also planar and traceable.
In addition, a fully 
-forested graph must have a vertex of degree 
. 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 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 for 
, 2, ... are 1, 1, 1, 1, 2, 2, 7, 13, 25, 17, ... (OEIS A380740).
