On the universal Grِbner bases of toric ideals of graphs

The universal Grِbner basis of an ideal is a Grِbner basis with respect to all term orders simultaneously. We characterize in graph theoretical terms the elements of the universal Grِbner basis of the toric ideal of a graph. We also provide a new degree bound. Finally, we give examples of graphs for which the true degrees of their circuits are less than the degrees of some elements of the Graver basis.