2
$\begingroup$

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 ?

$\endgroup$
1
$\begingroup$

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}\}$.

$\endgroup$
  • $\begingroup$ what is k in the min(bi,k) for the bipartition theorem ? So checking that the sum of degrees is not enough to ensure bipartite graph ? $\endgroup$ – calveeen Nov 17 '18 at 6:09
  • $\begingroup$ @calveeen $k$ is the variable, and the inequality must be true for all $1\le k\le n$. Yes, sum of degrees is not enough to ensure bipartite graph existence, but the above condition is enough. $\endgroup$ – Parcly Taxel Nov 17 '18 at 6:22
  • $\begingroup$ Just to check, this theorem only holds for checking bipartite graphs with equal number of vertices on both sets. It does not generalise if the sum of deg in one set = sum of deg in other set when both sets have unequal number of vertices ? $\endgroup$ – calveeen Nov 18 '18 at 1:12
  • $\begingroup$ @calveeen As I said, if the sets have unequal vertex counts, you can add degree-0 vertices to the smaller set to make things equal. $\endgroup$ – Parcly Taxel Nov 18 '18 at 2:39
  • $\begingroup$ All right sorry ! $\endgroup$ – calveeen Nov 18 '18 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.