Answer to Problem 21
The answer is no. From the theorem given earlier
("Your First Theorem In Graph Theory") and the
definition of a 3-regular graph, it can be seen that
the number of edges
in
a 3-regular graph has the below relation to the number
of vertices
:
Equation 8
Therefore,
Equation 9
Because every tree with
vertices has
edges, a graph with two spanning trees
without overlapping edges must have at least
edges.
Thus,
Equation 10
and, substituting for
,
Equation 11
implying that
.