On trivalent spines of surfaces Let $\Sigma$ be a surface with non-empty boundary labelled by finitely many points $x_i$.
For our purposes a spine $s$ for $\Sigma$ is a uni-trivalent graph embedded in $\Sigma$ whose 1-vertices are precisely the labelled points $x_i$, such that $\Sigma$ deformation retracts onto $s$.

Question:
Given a labelled surface $\Sigma$, are any two spines $s, s^\prime$ the same modulo isotopies in $\Sigma$ and the local skein relation

(the letters are just to keep track of the edges)?

Motivation: I want to use the spine lemma to pick a basis for the Turaev-Viro vector space for surfaces, and am trying to show that it doesn't matter which spine I pick for a given labelled surface.
I am particularly interested in the case where $\Sigma$ is the $n$-times punctured disk. (I'm writing an Honours thesis and one of the things we'd like to look at is the representation theory of the braid group on the Turaev-Viro module on such surfaces, where the group acts by permuting the holes.)
 A: You might be interested in this short paper of Hatcher:
http://www.math.cornell.edu/~hatcher/Papers/TriangSurf.pdf
There is a beautiful picture there concerning trivalent spines. Trivalent spines are dual to ideal triangulations, and ideal triangulations form the top-dimensional cells of a complex called arc complex. Two top-dimensional cells share a codimension-1 cell precisely when they are related by a flip, which is the dual of the move you draw.
Hatcher gives a nice topological proof that the arc complex is connected and even contractible, and every pair of triangulation are hence connected by a path of flips. Given that picture, you only have to worry about the 1-valent vertices.
The picture actually also tells you more: it tells you that two different paths connecting two triangulations are themselves connected by finitely many moves, the most important one being the pentagonal move that is crucial in quantum topology and corresponds in Turaev-Viro invariants to the 2-3 moves for 3-dimensional triangulations. (This part however is not developed in this paper of Hatcher.)
A: The answer is "yes".  I am a little pressed for time right now, so I'm going to restrict myself to the case where $\Sigma$ is a disc.  This will be a real pain to explain without pictures, so I suggest drawing what I am saying below.
The proof will be by induction on the number $n$ of vertices.  The base case is $n=2$, where the result is trivial.  Assume now that $n>2$.  Consider two spines $s_1$ and $s_2$ on $\Sigma$ with $n$ leaves $p_1,\ldots,p_n$ (arranged cyclically around the circle).  There are unique embedded edge paths $\rho$ and $\rho'$ in $s$ and $s'$ connecting $p_1$ to $p_2$.  Perform your moves to $s$ and $s'$ such that the lengths of $\rho$ and $\rho'$ (i.e. the number of edges they contain) is as small as possible.  
I claim that $\rho$ and $\rho'$ each have length $2$.  Indeed, the path $\rho$ divides $\Sigma$ into two sub-discs.  One of these (call it $D$) has boundary consisting of $\rho$ together with the arc from $p_1$ to $p_2$ on $\partial \Sigma$ that does not contain any other $p_i$'s.  The key observation is that $D$ cannot contain any points of $s$ in its interior.  If $\rho$ has more than two edges in it, you can perform one of your local moves on an interior edge and shrink $\rho$ (this shrinks $\rho$ since the portion of $\rho$ on your "local move" has to be on "one side" -- draw the picture!).  A similar things holds for $\rho'$.
So now $\rho$ and $\rho'$ consist of two edges.  Isotoping $s$ and $s'$, we can assume that in fact $\rho = \rho'$.  Let $q$ be their common interior vertex.  We can delete the two edges of $\rho$ from $s$ and collapse a small disc on the circle to get a new spine $\hat{s}$ on a disc with $(n-1)$ leaves $q,p_3,\ldots,p_n$.  Similarly, we can delete the two edges of $\rho'$ from $s'$ and collapse a small disc on the circle to get a new spine $\hat{s}'$ on a disc with $(n-1)$ leaves $q,p_3,\ldots,p_n$.  By induction, we can connect $\hat{s}$ and $\hat{s}'$ using your local moves.  Putting $\rho$ and $\rho'$ back, we get a sequence of moves connecting $s$ and $s'$.
