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
  • 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
    Commented Sep 17, 2018 at 5:34

1 Answer 1

1
$\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$
4
  • $\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$ Commented Sep 17, 2018 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$ Commented Sep 17, 2018 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
    Commented Sep 17, 2018 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$ Commented Sep 17, 2018 at 22:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .