Isomorphism classes of trees with maximum degree $3$ and $6$ vertices

discrete mathematicsgraph theorygraph-isomorphismtrees

List the isomorphism classes of trees with maximum degree $3$ and $6$ vertices.

I start with the star $K_{1,3}$ and append vertices accordingly to achieve $6$ vertices keeping maximum degree $3$. I found exactly $3$ classes for the case, $G_1,G_2,G_3$, which are-

However, the book doesn't mention $G_3$ as a possible class and I am unable to see why. It is a connected acyclic graph with $6$ vertices and maximum degree $3$ and doesn't seem to be isomorphic to the other graphs since there are $2$ vertices with degree $2$.

EDIT
Attaching the provided question plus solution in case, something trivial was overlooked.


Note that my question is specific to the case $k=3$ and $n=6$.

Best Answer

I think that both graphs $G_1$ and $G_3$ are included in the definition of $Q$. The word "growing" a leaf might be the key factor here. With "growing" we do not mean to add a single leaf, but to add a single path to a neighbour of a leaf.

Consider the path on $5$ vertices $v_1-v_2-v_3-v_4-v_5$.

For $G_1$ add an edge $(v_2,v_6)$ (or $v_4,v_6$). We append a leaf from a neighbour of a leaf, namely from the leaf $v_1$ (or $v_5$) and the diameter is $4$. This is the same as growing a $P_1$.

For $G_3$ add an edge $(v_3,v_6)$. Here we grow a leaf from a neighbour of a leaf as well.

Notice that for $T_{i,j}$ the author explicitly says "appending" leaves to the endpoints of the edge.

This slightly adjusted picture might help (excuse my poor drawing).

enter image description here

If this is not the correct explaination, then your answer is still correct (for the reasons you have provided) and the author made a mistake. To be 100% sure, we can always consult sage by running the following code

from sage.graphs.trees import TreeIterator

for t in TreeIterator(6):
    if t.degree_sequence()[0] == 3:
        t.show()

yielding to

enter image description here