  We study semigroups of labellings associated to a graph. These generalize the
Jukes-Cantor model and phylogenetic toric varieties defined by Buczy\'nska. Our
main theorem bounds the degree of the generators of the semigroup by g+1 when
the graph has first Betti number g. Also, we provide a series of examples where
the bound is sharp.
