Draw bipartite graph with degree sequence (5,5,5,5,4,4,4,4,4,4,4,4,4,4)

Question

I was wondering that since (5,5,5,5,4,4,4,4,4,4,4,4,4,4) can be split into a first set (5,5,4,4,4,4,4) and 2nd set (5,5,4,4,4,4,4). It satisfies the condition that the degrees of the first set = degrees of 2nd set, but i still cant draw a bipartite graph with this. So my general question is that if a graph is bipartite then the sum of degrees in one vertex set = sum of degrees in the other vertex set. But the reverse is not true ?

If the reverse is not true, is there a method to know if you can construct a bi partite graph from the degree sequence without actually trying to draw it out ?

Answer 1

Pairs of degree sequences for which there exists a bipartite graph whose bipartitions have those degree sequences are called bigraphic and are characterised by the Gale–Ryser theorem:

Let the two bipartitions' degree sequences be $(a_1,\dots,a_n)$ and $(b_1,\dots,b_n)$, where the $a_i$ are decreasing. There exists a bipartite graph whose bipartitions' degree sequences are as given if and only if $\sum_ia_i=\sum_ib_i$ (the sum-of-degrees condition) and for all $1 \le k\le n$, $$\sum^k_{i=1} a_i\le \sum^n_{i=1} \min(b_i,k)$$

Cases where the bipartitions have different numbers of vertices can be handled by adding degree-0 vertices to the smaller bipartition. As a simple example, there is no bipartite graph with degree sequences of its bipartitions $(3,2)$ and $(3,2)$ because the inequality is not satisfied for $k=1$.

For the given sequences of two 5s and five 4s on both sides, since those sequences satisfy the given inequalities (as you may check yourself), the desired bipartite graph exists. Indeed, we can construct it easily: take the 14 vertices as $v_i$ and the edges as $v_iv_{i+1}$, $v_iv_{i+3}$, $v_0v_5$ and $v_2v_7$ ($0\le i<14$ and the indices are taken modulo 14). Then the bipartitions are the vertices with even indices $\{v_0,v_2,\dots,v_{12}\}$ and those with odd indices $\{v_1,v_3,\dots,v_{13}\}$.