Let $G=(V,E) $ be a series parallel graph (definition) with terminals $s,t \in V$
Prove that for every vertex $v \in V v\neq s,t $ it is true that $deg(v)\ge 2$ and that there exists one vertex such that $deg(v)=2$
How would I prove that ? My first thought was to use induction over the decomposition tree $T(G)$. The base case with $T(G)$ having only one node is trivial but I don't know how to perform the induction step
Would appreciate any help
Derive the series-parallel directed graph in the usual way. In this case, $deg(v)$ should be the in-degree plus the out-degree. From there, it's a matter of proving there is a path from $s$ to $v$ and a path from $v$ to $t$. We can contradict this if $deg(v)<2$. Let me know if you would like more details to the proof.