# 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?

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.

• If $p$ is the number of vertices in $G$, what is the number of edges in $G$? What is the sum of the degrees of all the vertices?
– bof
Commented Sep 17, 2018 at 5:34

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.$
• you lose me at "Since each vertex has degree 3 or 4, this means that G has 4 vertices of degree 3." I see that $4 | (4p - 4) \implies p_3 = 4n, n \in \mathbb{N}$ but i don't see anything that fixes this value for $p_3 = 4$ as the number of vertices with degree 3 Commented Sep 17, 2018 at 13:38
• Nevermind I see it but you should write out the equation involving $p_3$ and $p_4$, the number of vertices of degree n for $p_n$ and solve it before I accept your answer Commented Sep 17, 2018 at 13:48