  This paper is concerned with the topological invariant of a graph given by
the maximum degree of a Markov basis element for the corresponding graph model
for binary contingency tables. We describe a degree four Markov basis for the
model when the underlying graph is a cycle and generalize this result to the
complete bipartite graph $K_{2,n}$. We also give a combinatorial classification
of degree two and three Markov basis moves as well as a Buchberger-free
algorithm to compute moves of arbitrary given degree. Finally, we compute the
algebraic degree of the model when the underlying graph is a forest.
