3
$\begingroup$

This is a question from the Graph Theory (Bondy & Murty) text which has me rather stumped.

Let $p = (p_1, p_2, . . . , p_m)$ and $q = (q_1, q_2, . . . , q_n)$ be two sequences of nonnegative integers. The pair $(p, q)$ is said to be realizable by a simple bipartite graph if there exists a simple bipartite graph G and a bipartition $(\{x_1, x_2, . . . , x_m\}, \{y_1, y_2, . . . , y_n\})$ such that $\deg(x_i) = p_i$ for $1 ≤ i ≤ m$, and $\deg(y_j) = q_j$ for $1 ≤ j ≤ n.$

(a) Formulate as a network flow problem the problem of determining whether a given pair $(p, q)$ is realizable by a simple bipartite graph.

(b) Suppose that q_1 ≥ q_2 ≥ · · · ≥ q_n. Deduce from the Max-Flow Min-Cut Theorem that $(p, q)$ is realizable by a simple bipartite graph if and only if $\sum\limits_{i=1}^m p_i = \sum\limits_{j=1}^n q_j$ and $\sum\limits_{i=1}^m \min(p_i, k) \geq \sum\limits_{j=1}^k q_j$ for $1 \leq k \leq n$

For (a), we view each $x_i$ as a source and each $y_j$ as a sink and connect as follows (edge $(x_i,y_j)$ as allowed from $p$ and $q$ with capacity = 1 for all edges). Not 100% sure how to go about with the flows but I believe we can claim that it is realized if the constructed network has a feasible flow.

I am rather unsure how to go about doing (b) from the max-flow min-cut theorem (apologies for my lack of progress).

Edit: upper bound of sigma of $q_j$ in inequality of part b to k, not n.

1 Answers 1

2

I assigned just this question on a problem set recently- you can find the answer on the first page of the Problem Set 3 solutions.