Cubic Trees in graph theory

Question

A tree in graph theory would be called "Cubic" If every non-leaf vertex has degree 3. Are there any cubic trees with "even" number of edges?

I have tried different patterns yet it gives me odd number of edges, Are an even number of edges possible?

Answer 1

You can use the fact that a tree has one fewer edge than nodes ($m=n{-}1$).

Suppose the cubic tree has $\ell$ leaves out of $n$ nodes. Then by the degree sum of nodes, $\ell + 3(n-\ell)$, the number of edges $m = (\ell + 3(n-\ell))/2$; then

$n-1=(\ell + 3(n-\ell))/2 \\ 2n-2 = 3n-2\ell \\ 2\ell - 2 = n $

Thus the number of nodes $n$ is even and the number of edges is odd. As a bonus, the number of interior nodes is two less than the number of leaves, $n{-}\ell = \ell{-}2$.

Answer 2

Start at a leaf, and count one edge. Either you are done, or there are two edges meeting the one you already have. Those two edges mark out a further two vertices. Each vertex you visit if you keep going has either zero or two more edges to count. The tree is connected so you visit each vertex this way. At each stage you add an even number of edges, and you started with one, so the final total will be odd.

Answer 3

Take a cubic tree, and pull off a leaf. This leaves a tree, but with one bad vertex, of degree $2$. Merge together the edges emerging from this vertex, and you get a cubic tree, with two fewer edges. Now use induction.