For the rest of this problem, let G be a finite simple bipartite graph with bipartition V(G) = X U Y.

(a) Suppose that every vertex in G has at least one neighbor, and that for all x X and y Y, if xy E(G), then deg(x) >= deg(y). Show that |X|

(b) Suppose that every vertex in X (resp. Y) is adjacent to at least one but not all of the vertices in Y (resp. X), and that for all x X and y Y, if xy not E(G), then deg(x) >= deg(y). Show that |X| Problem 4. Double counting in bipartite graphs. A bipartition of a graph G is a partition VG) = XUY of its vertex set such that every edge of G joins a vertex in X to a vertex in Y. A graph G is bipartite if it has a bipartition. When working with a bipartite graph G, the following observation is often useful: If w:XX Y R is an arbitrary weight function, then [ w(x, y) = I w(x, y). XyEY yEY EX (This is just double counting, of course.) For the rest of this problem, let G be a finite simple bipartite graph with bipartition V(G) = XUY. (a) Suppose that every vertex in G has at least one neighbor, and that for all x X and y e Y, if xy E(G), then degg(x) > degg(y). Show that (XIHint. Assign a weight w to each edge xy so that for all x e X, EyENG (x) w(xy) = 1. (b) Suppose that every vertex in X (resp. Y) is adjacent to at least one but not all of the vertices in Y (resp. X), and that for all x X and y e Y, if xy & E(G), then degg(x) > degg(y). Show that (XI Y. Problem 4. Double counting in bipartite graphs. A bipartition of a graph G is a partition VG) = XUY of its vertex set such that every edge of G joins a vertex in X to a vertex in Y. A graph G is bipartite if it has a bipartition. When working with a bipartite graph G, the following observation is often useful: If w:XX Y R is an arbitrary weight function, then [ w(x, y) = I w(x, y). XyEY yEY EX (This is just double counting, of course.) For the rest of this problem, let G be a finite simple bipartite graph with bipartition V(G) = XUY. (a) Suppose that every vertex in G has at least one neighbor, and that for all x X and y e Y, if xy E(G), then degg(x) > degg(y). Show that (XIHint. Assign a weight w to each edge xy so that for all x e X, EyENG (x) w(xy) = 1. (b) Suppose that every vertex in X (resp. Y) is adjacent to at least one but not all of the vertices in Y (resp. X), and that for all x X and y e Y, if xy & E(G), then degg(x) > degg(y). Show that (XI Y