We study semigroups of labellings associated to a graph. These generalise the Jukes-Cantor model and phylogenetic toric varieties defined in [Buczyńska W., Phylogenetic toric varieties on graphs, J. Algebraic Combin., 2012, 35(3), 421–460]. 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.