0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – bof Sep 17 '18 at 5:34
0
$\begingroup$

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.$

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – rjm27trekkie Sep 17 '18 at 13:38
  • $\begingroup$ 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 $\endgroup$ – rjm27trekkie Sep 17 '18 at 13:48
  • $\begingroup$ It's not enough that I give you enough hints so you can finish the solution by yourself? You want me to write out the complete solution in a form that's ready to hand in? OK, when is this due? $\endgroup$ – bof Sep 17 '18 at 21:35
  • $\begingroup$ No, you misunderstand. I'd write it myself, but the biggest problem mathematicians have is not explaining themselves clearly because something is obvious to them, but not to others. I want you to earn the rep that you get by providing a quality answer that anyone can understand. Not just the elite few that already know how to think about graph theory at a reasonably high level. Your edit is much better. $\endgroup$ – rjm27trekkie Sep 17 '18 at 22:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.