I have to prove that the clique-width of a tree is not greater that 3, without using the theorem which connects the tree-width and clique-width. I have to show that it's enough to construct any tree using 3-expression.
I tried to do it with induction but I wasn't succesfull. The thing is that I easily understoon for paths and cycles because I know their shape, but trees aren't that unique when it comes to their construction. Any hints on how to approach this problem?
Suppose we have a set $L$ of $3$ labels, which we can use in a $3$ expression to construct the tree $T$. Recall that we are allowed to take the disjoint union of two labeled graphs in the operations allowed for clique-width.
We will prove a slightly stronger statement: let $r$ be any vertex of $T$ and let $a,b \in L$ with $a \neq b$. Then $T$ can be constructed from a $3$-expression such that $r$ is labeled $a$, and every other vertex is labeled $b$.
This can be proved by induction. As a base case, if $T$ has only one vertex, this is trivial. Assume $T$ has at least two vertices. Let $c$ be the label of $L$ distinct from $a$ and $b$, and let $s$ be a neighbor of $r$ in $T$.
By removing the $rs$ edge, two trees $T_1$ and $T_2$ are obtained.
I actually had the rest of the proof written, but I see you're asking for hints rather than an answer.
This should get you started, as you can use induction to construct $T_1$ and $T_2$ and join them together to get the desired properties.