# Practice exercise | Trees | Graph theory

Let $$G$$ be a tree with 14 vertices of degree 1, and the degree of each nonterminal vertex is 4 or 5. Find the number of vertices of degree 4 and degree 5.

My attempt, summarized, is the following: Let $$x$$ be the number of vertices of degree 4, let $$y$$ be the number of vertices of degree 5. Note that there are $$x + y + 14$$ vertices ($$x + y + 13$$ edges, since $$G$$ is a tree), then $$4x + 5y + 1 (14) = 2x + 2y + 26$$ applying handshaking lemma (the sum over all vertices of the degrees is two times the number of edges). But the solution to this is $$x = - \frac{3}{2} y + 6$$. I don't know if it's okay or what I'm doing wrong.

You were on the right track.

From $$4x + 5y + 14 = 2x + 2y + 26$$ we get $$2x+3y=12$$ It follows that $$y$$ is even and at most $$4$$, hence $$(x,y)\in\bigl\{(0,4),\;(3,2),\;(6,0)\bigr\}$$ As we'll show, all $$3$$ of these potential pairs $$(x,y)$$ are, in fsct, possible.

The image below shows an example with $$(x,y)=(0,4)$$. And the image below shows an example with $$(x,y)=(3,2)$$. Finally, the image below shows an example with $$(x,y)=(6,0)$$. Thus, as claimed, each of the pairs $$(x,y)=(0,4),\qquad(x,y)=(3,2),\qquad(x,y)=(6,0)$$ can actually be realized.

What you have done is correct so far. Now since $$x\geq0$$, we have $$6-\frac32y\geq0\implies y\leq4$$ Also, $$x$$ is an integer, so $$y$$ must be even. This gives the solutions $$y=4,\ x=0\\y=2,\ x=3\\y=0,\ x=6$$

These are the only possibilities. We must investigate whether any such tree actually exist. Notice that the subgraph induced by the non-terminal nodes must be a tree, for in the original graph, if all the neighbors of a non-terminal node had degree $$1$$, the graph would not be connected. Once we have this induced tree, and the degrees of the vertices in the original graph, the original graph is determined, because we just have to add enough terminal nodes to bring the vertex degrees up to the required value.

That isn't stated very very, I know, but examples will make it clear, I hope. I'll use $$F$$ to mean a vertex of degree four, and $$V$$ (Roman $$5$$) for a vertex of degree $$5$$. I'll use a hyphen (-) do indicate an edge in the induced subtree.

In the case $$y=4,\ x=0$$ we have the induced subgraph $$V-V-V-V$$. Two of the vertices have degree $$1$$ in the subtree, so we'll add $$4$$ terminal vertices to each of them. The other two vertices have degree $$2$$ in the subtree, and we will add $$3$$ terminal vertices to each. This gives $$14$$ terminal vertices, as required.

In the case $$y=2,\ x=3$$, we can use $$F-V-F-V-F$$ as the subtree. We will add $$3$$ terminal vertices to each node except for the $$f$$ in the middle, where we add $$2$$.

In the case $$y=0,\ x=6$$, the subtree $$F-F-F-F-F-F$$ works. We add $$3$$ terminal vertices to the nodes on the ends, and $$2$$ to the other $$4$$ nodes.

Actually, a little thought shows that, so long as the induced subgraph of $$F$$ and $$V$$ nodes form a tree $$T$$, and there is no $$F$$ node of degree greater than $$4$$ in $$T$$, nor a $$V$$ node of degree greater than $$%$$, then filling in the terminal nodes as above will produce a suitable tree. We can therefore list all the solutions, if we cared to.

The smallest such graph has two degree 5 and one degree 4 vertices.
Larger graphs with 14 terminal vertices are numberous.

• The sum of the vertex degrees is $28$, so this graph has $14$ edges and $17$ vertices, and is not connected. – saulspatz Apr 11 at 3:49