A graph G has only vertices of degree 3 and degree 4 and is decomposable into two spanning trees. How many vertices of degree 3 are in G?
I know that $\exists$ 2 spanning trees in the graph G with $p=q+1$ where $p$ is the number of vertices in the tree (the same as $p$ for G since it is spanning) and $q$ is the number of edges in the tree. How can I use this to get a result for the number of vertices with degree 3 in G.
Best Answer
If $G$ has $p$ vertices and is decomposable into two spanning trees, then each tree has $p-1$ edges, so $G$ has $2p-2$ edges. Therefore the degrees of all vertices of $G$ add up to $4p-4.$
If a graph has $p$ vertices, and each vertex has degree $3$ or $4$, then the sum of the degrees is $4p-x$ where $x$ is the number of vertices of degree $3.$ In your graph $G$ you have $4p-x=4p-4,$ so $x=4.$