Bipartite graphs

Result 1. Proof. Given a bipartition (X, Y), color X with 1 and Y with 2: every edge has one end of each color, so the coloring is proper. Given a proper coloring with colors 1 and 2, let X be the vertices colored 1 and Y the rest. No edge joins two vertices of one color, so every edge runs between X and Y. \square

Result 2. Proof. A vertex of the part of size m is joined to the n vertices of the other part and to nothing else, so it has degree n; likewise the others have degree m. Each of the m vertices meets n edges, and each edge has exactly one end in that part, so there are m \cdot n edges. \square

Result 3. Proof. \sum_{x \in X} \deg(x) counts the pairs (a vertex x \in X, an edge at x). Every edge has exactly one end in X, so it is counted exactly once. The same holds for Y. \square

Result 4. Proof. Suppose G is bipartite and (v_0, v_1, \ldots, v_k = v_0) is a cycle. Each edge changes part, so by induction on i, v_i lies in the part of v_0 exactly when i is even. Since v_k = v_0, k is even.

Now suppose G has no odd cycle. In each component H choose a vertex r_H, and put a vertex v of H in X when d(r_H, v) is even and in Y when it is odd; the distance is finite, since H is connected. An edge uv has both ends in one component H. Suppose a = d(r_H, u) and b = d(r_H, v) had the same parity. A shortest walk from r_H to u, then the edge uv, then a shortest walk from v back to r_H, is a closed walk of length a + b + 1, which is odd because a + b is even. By Result 5 of Walks, paths, cycles and connected graphs it contains an odd cycle, which is impossible. So every edge joins an even distance to an odd one, and (X, Y) is a bipartition. \square

Result 5. Proof. A forest has no cycle at all, so Result 4 applies; in a tree, the parity of the level gives the parts directly (Trees, Result 10). C_n is a cycle of length n, so for odd n it is not bipartite, and for even n it is 2-colorable (Graph coloring, Result 3). In a grid, put (i, j) in X when i + j is even: an edge changes one coordinate by 1 and so the parity of i + j. In Q_n, put a string in X when it has an even number of 1s: changing one place changes the number of 1s by one. A triangle is an odd cycle. \square

Result 6. Proof. Let the parts have a and n - a vertices. Each edge is a pair (a vertex of X, a vertex of Y) and different edges give different pairs, so

and \lvert E \rvert is an integer. For n = 2k, K_{k,k} has \displaystyle k^2 = \frac{n^2}{4} edges; for n = 2k + 1, K_{k,k+1} has \displaystyle k^2 + k = \left\lfloor k^2 + k + \frac{1}{4} \right\rfloor edges, which is \displaystyle \left\lfloor \frac{n^2}{4} \right\rfloor. \square

Result 7. Proof. Let M cover X, and call the other end of the edge of M at x the partner of x. For S \subseteq X, the partners of the vertices of S lie in N(S), and no two edges of M share an end, so they are \lvert S \rvert different vertices. \square

1. Not bipartite; (b, c, d, e, f, b) is a cycle of length 5. Layers: \{a\}, \{b, g\}, \{c, f\}, \{d, e\}, and de joins two vertices of layer 3. Closing (a, b, c, d) and (a, g, f, e) with de gives the 7-cycle (a, b, c, d, e, f, g, a).
2. Exactly when n is even. For odd n, (0, 1, \ldots, n - 1, 0) is an odd cycle. For even n, put i in X when i is even and i' in X when i is odd: the edges i(i + 1) and i'(i + 1)' change parity (from n - 1 to 0 too, as n is even), and ii' runs between parts.
3. m = 3, n = 8. They are the roots of t^2 - 11t + 24 = (t - 3)(t - 8).
4. \binom{m}{2}\binom{n}{2}, which is 3 \cdot 6 = 18 for K_{3,4}. A 4-cycle alternates parts, so it uses two vertices x, x' of one part and two y, y' of the other, and each such choice gives exactly one cycle, (x, y, x', y', x).
5. 8 vertices in Y and 24 edges. By Result 3, \lvert E \rvert = 6 \cdot 4 = 24 = 3\lvert Y \rvert.
6. No. Result 3 would give both 5 \cdot 3 = 15 edges and 7 \cdot 3 = 21 edges.
7. 42 edges, by K_{6,7}. \displaystyle \left\lfloor \frac{169}{4} \right\rfloor = 42 = 6 \cdot 7, and by Exercise 13 no other bipartite graph on 13 vertices has 42.
8. 5 and 7, or 6 and 6. Parts a and 12 - a need a(12 - a) \ge 35: 5 \cdot 7 = 35 and 6 \cdot 6 = 36 work, but 4 \cdot 8 = 32 does not.
9. s_1 Q, s_2 R, s_3 P, s_4 T. s_3 must take P, so s_1 must take Q, so s_2 must take R, so s_4 must take T: every step was forced.
10. No; at most 5. S = \{s_1, s_2, s_3, s_4\} has N(S) = \{A, B, C\}, so at most 3 of them are covered. s_1 A, s_2 B, s_3 C, s_5 E, s_6 D covers five.
11. X = \{x\}, Y = \{y_1, y_2\}, edges xy_1, xy_2. \{x\} has 2 neighbors, but N(Y) = \{x\} has 1 < 2 vertices.
12. Let (X, Y) be a bipartition and r \in X (swap names if needed). For any v, a path of length d(r, v) from r to v changes part at every step, so v \in X exactly when d(r, v) is even. So X and Y are fixed by r alone.
13. In the proof of Result 6, equality needs \displaystyle a(n - a) = \left\lfloor \frac{n^2}{4} \right\rfloor, so \displaystyle \left(a - \frac{n}{2}\right)^2 < 1 (any other a gives at least 1 for even n, at least \displaystyle \frac{9}{4} for odd n). That forces a = \lfloor n/2 \rfloor or \lceil n/2 \rceil, and \lvert E \rvert = a(n - a) means every pair (a vertex of X, a vertex of Y) is an edge.
14. For i \ne j, i + j \ge 3, so a prime i + j is odd and i, j have opposite parity. The even numbers and the odd numbers are a bipartition.
15. K_4 on 1, 2, 3, 4: the 4-cycle (1, 2, 3, 4, 1) passes through every vertex, but (1, 2, 3, 1) is a triangle, so by Result 4 K_4 is not bipartite.
16. For S \subseteq X, at least d\lvert S \rvert edges have an end in S, and each has its other end in N(S). The vertices of N(S) are ends of at most d\lvert N(S) \rvert edges, so d\lvert S \rvert \le d\lvert N(S) \rvert and \lvert N(S) \rvert \ge \lvert S \rvert. Hall’s theorem gives the matching.
17. A perfect matching of K_{n,n} gives each of x_1, \ldots, x_n a different partner in Y, and every such choice is a perfect matching, since all pairs are edges. The partner of x_1 can be chosen in n ways, of x_2 in n - 1, and so on: n! in all.