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 .