Counting degree sequences of spanning trees in bipartite graphs: A graph-theoretic proof

摘要

Given a bipartite graph G = (S (boolean OR) over dot T, E) with bipartition S, T each spanning tree in G has a degree sequence on S and one on T. Lohne and Rudloff showed that the number of possible degree sequences on S equals the number of possible degree sequences on T. Their proof uses a non-trivial characterization of degree sequences by G-draconian sequences based on polyhedral results of Postnikov. In this paper, we give a purely graph-theoretic proof of their result.