MathCastle
Graph TheoryChallengeBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Challenge problem

Of the following five pairs of degree sequences for a bipartite graph (written as (row sums, column sums)), how many can actually be realized by SOME bipartite graph? (1) (3,3,3),(3,3,3)(3,3,3),(3,3,3). (2) (3,3,3),(2,2,2)(3,3,3),(2,2,2). (3) (2,2,2,2),(3,3,1,1)(2,2,2,2),(3,3,1,1). (4) (4,1,1,1,1),(4,1,1,1,1)(4,1,1,1,1),(4,1,1,1,1). (5) (3,2,2,1),(3,2,2,1)(3,2,2,1),(3,2,2,1).