Bipartite graphs and matchings (intro) - Discrete Math

In a bipartite graph $G = (X \cup Y, E)$ , let $S \subseteq X$ with $|S| = 4$ . If $|N(S)| = 3$ , where $N(S)$ denotes the neighborhood of $S$ in $Y$ , and $G$ has a matching that saturates all vertices in $X \setminus S$ , what is the maximum possible size of a matching in $G$ ?
Answer: $|X| - 1$ When analyzing matching problems in bipartite graphs, you need to understand how Hall's Marriage Theorem and its implications work. This question tests your ability to find the maximum matching when there's a bottleneck in the graph structure. The key insight is that we have a subset $S \subseteq X$ with $|S| = 4$ vertices, but their neighborhood $N(S)$ has only 3 vertices. This creates a fundamental limitation: at most 3 vertices from $S$ can be matched, since there are only 3 possible partners for them in $Y$ . This means at least 1 vertex from $S$ must remain unmatched in any matching. Since $G$ has a matching that saturates all vertices in $X \setminus S$ (meaning all vertices in $X$ except those in $S$ are matched), we can match $|X| - 4$ vertices from $X \setminus S$ plus at most 3 vertices from $S$ . This gives us a maximum matching of size $(|X| - 4) + 3 = |X| - 1$ , making choice A correct. Choice B ( $|X| - 4$ ) incorrectly assumes no vertices from $S$ can be matched. Choice C ( $|X| - 3$ ) mistakenly thinks all 4 vertices in $S$ can be matched despite the neighborhood constraint. Choice D ( $\min(|X|, |Y|) - 1$ ) applies a general upper bound without considering the specific bottleneck created by $S$ and $N(S)$ . Remember: In bipartite matching problems, always check for Hall's condition violations. When $|N(S)| < |S|$ for some subset $S$ , you've found the bottleneck that determines the maximum matching size.
In a bipartite graph $G = (A \cup B, E)$ where $|A| = n$ and $|B| = n-1$ , every vertex in $A$ has degree 2 and every vertex in $B$ has degree greater than 2. If $G$ has a matching of size $n-1$ , which statement about the structure of $G$ must be true?
Answer: Hall's condition holds with equality $|N(S)| = |S|$ for at least one proper subset $S \subseteq A$ Since |A| = n and |B| = n-1, a maximum matching has size n-1, leaving exactly one vertex in A unmatched. For this maximum to be achieved, Hall's condition |N(S)| ≥ |S| must hold for all subsets S ⊆ A. Given the tight constraint (only n-1 vertices in B to match n vertices in A), there must exist at least one subset S where |N(S)| = |S|, creating a bottleneck that forces exactly one vertex in A to remain unmatched.
A bipartite graph has vertex sets $U = \{u_1, u_2, u_3, u_4\}$ and $V = \{v_1, v_2, v_3, v_4\}$ . If the graph has a perfect matching $M_1 = \{(u_1,v_2), (u_2,v_4), (u_3,v_1), (u_4,v_3)\}$ and another perfect matching $M_2 = \{(u_1,v_3), (u_2,v_1), (u_3,v_4), (u_4,v_2)\}$ , what is the minimum number of edges the graph must contain?
Answer: 8 The graph must contain all edges from both perfect matchings $M_1$ and $M_2$ . Since $M_1 = \{(u_1,v_2), (u_2,v_4), (u_3,v_1), (u_4,v_3)\}$ and $M_2 = \{(u_1,v_3), (u_2,v_1), (u_3,v_4), (u_4,v_2)\}$ , and these two sets are disjoint (no edge appears in both matchings), the graph must have at least $|M_1| + |M_2| = 4 + 4 = 8$ edges. Choice A represents only one perfect matching. Choice B incorrectly assumes some edges are shared between the matchings. Choice D overestimates by assuming additional edges are needed beyond those in the two given perfect matchings.
In a bipartite graph $G = (X \cup Y, E)$ , suppose there exists a matching $M$ that covers all vertices in $X$ but leaves exactly 2 vertices in $Y$ unmatched. If $|Y| = |X| + 2$ , and we add one new vertex $x'$ to $X$ along with edges connecting $x'$ to the 2 unmatched vertices in $Y$ , what can we conclude about perfect matchings in the resulting graph $G'$ ?
Answer: $G'$ definitely has a perfect matching extending the original matching $M$ In the original graph, $M$ covers all of $X$ and all but 2 vertices of $Y$ . After adding $x'$ to $X$ and connecting it to the 2 unmatched vertices in $Y$ , we have $|X \cup \{x'\}| = |X| + 1$ and $|Y| = |X| + 2$ , so the new graph has equal-sized partitions. We can extend $M$ to a perfect matching by adding one edge from $x'$ to either of the 2 previously unmatched vertices in $Y$ . Choice B is wrong because the sizes are now balanced. Choice C is incorrect because we can always extend the existing matching $M$ . Choice D is wrong because while $x'$ could connect to either unmatched vertex, this doesn't guarantee exactly two perfect matchings total.
Let $G$ be a bipartite graph with bipartition $(X, Y)$ where $|X| = 7$ and $|Y| = 5$ . If $G$ has a matching of size 4, and we know that removing any single vertex from $Y$ reduces the maximum matching size to at most 3, what can we conclude about the structure of $G$ ?
Answer: At least two vertices in $Y$ are essential for achieving matching size 4 Since the maximum matching has size 4 and removing any single vertex from $Y$ reduces this to at most 3, this means that no single vertex in $Y$ is solely responsible for the fourth matched edge. If only one vertex in $Y$ were essential, removing just that vertex would drop the matching size to 3, but removing others would maintain size 4. Since removing ANY vertex from $Y$ causes this drop, multiple vertices in $Y$ must be critical for achieving the full matching size of 4. Choice A confuses matching edges with vertex degrees. Choice B contradicts the given condition that removing ANY vertex causes the reduction. Choice D makes an unjustified claim about uniqueness.
Let $M_1$ and $M_2$ be two different maximum matchings in a bipartite graph $G$ . If $|M_1| = |M_2| = k$ and $|M_1 \cap M_2| = k-2$ , how many connected components does the symmetric difference $M_1 \triangle M_2$ induce in $G$ ?
Answer: 2 Since |M₁ ∩ M₂| = k-2, there are 2 edges in M₁ but not M₂, and 2 edges in M₂ but not M₁. The symmetric difference M₁ ⊕ M₂ contains exactly 4 edges. In a bipartite graph, the symmetric difference of two matchings forms a collection of alternating paths and cycles. With 4 edges total, we must have exactly 2 connected components (either 2 paths of length 2, or 1 path of length 3 and 1 isolated edge, etc.).
A company wants to assign 8 employees to 6 projects. Each employee is qualified for exactly 3 projects, and each project requires exactly 4 qualified employees to choose from. If this situation is modeled as a bipartite graph, what can be concluded about the existence of an assignment where each project gets exactly one employee?
Answer: Such an assignment may exist depending on which specific qualifications each employee has This asks for a matching that saturates all 6 projects. By the handshaking lemma, the degree conditions (8×3 = 24 total edges = 6×4) are consistent. However, Hall's condition for the project side requires checking that every subset of projects has sufficiently many qualified employees. The given constraints don't guarantee this - it depends on the specific qualification pattern.
In a bipartite graph $G = (A \cup B, E)$ with $|A| = 6$ and $|B| = 6$ , suppose that for some subset $S \subseteq A$ with $|S| = 4$ , the neighborhood $N(S)$ has exactly 3 vertices. What can be concluded about perfect matchings in $G$ ?
Answer: $G$ has no perfect matching due to Hall's condition violation Hall's Marriage Theorem states that a bipartite graph $G = (A \cup B, E)$ has a matching that saturates $A$ if and only if for every subset $S \subseteq A$ , we have $|N(S)| \geq |S|$ . Here, we have a subset $S \subseteq A$ with $|S| = 4$ but $|N(S)| = 3$ , violating Hall's condition since $3 < 4$ . This means there is no matching that saturates $A$ , and therefore no perfect matching exists. Choice A ignores the Hall condition violation. Choice C is incorrect because finding one violating subset is sufficient to conclude no perfect matching exists. Choice D is wrong because the maximum matching size could be less than 5 due to this bottleneck.
Let $G$ be a bipartite graph with parts $A$ and $B$ where $|A| = |B| = 6$ . If $G$ has exactly 20 edges and every vertex has degree at least 2, which of the following statements about perfect matchings in $G$ is necessarily true?
Answer: $G$ may or may not contain a perfect matching depending on edge distribution With 20 edges and minimum degree 2, we have average degree 20/6 ≈ 3.33 per vertex. While this suggests good connectivity, Hall's condition depends on the specific edge distribution. We can construct examples where Hall's condition fails (violating perfect matching existence) and others where it holds, both satisfying the given constraints.
A bipartite graph $G = (L \cup R, E)$ has the property that every vertex in $L$ has degree 2 and every vertex in $R$ has degree 3. If $|L| = 9$ , what is $|R|$ , and what is the size of the maximum matching in $G$ ?
Answer: $|R| = 6$ and maximum matching size is 6 Using the handshaking lemma for bipartite graphs: the total degree from $L$ equals the total degree from $R$ . Total degree from $L$ is $9 \times 2 = 18$ . If every vertex in $R$ has degree 3, then $|R| \times 3 = 18$ , so $|R| = 6$ . For the maximum matching size: since $|L| = 9$ and $|R| = 6$ , the maximum possible matching size is $\min(9,6) = 6$ . The degree conditions ensure this maximum is achievable. Choice B has the correct $|R|$ but wrong matching size (can't exceed $\min(|L|,|R|)$ ). Choice C has wrong $|R|$ . Choice D has both wrong $|R|$ and impossible matching size.
Consider two bipartite graphs $G_1 = (X_1 \cup Y_1, E_1)$ and $G_2 = (X_2 \cup Y_2, E_2)$ where $|X_1| = |X_2| = 4$ , $|Y_1| = |Y_2| = 4$ , and both have perfect matchings. If we form a new bipartite graph $H$ by taking the disjoint union and adding exactly one edge between $Y_1$ and $X_2$ , what can we conclude about the maximum matching size in $H$ ?
Answer: The maximum matching size is 8, same as the sum of the original maximum matchings When analyzing matching problems in graph theory, you need to understand how structural changes affect maximum matching sizes. A matching is a set of edges with no shared vertices, and in bipartite graphs, the maximum matching size is constrained by the smaller partition. Let's trace through what happens when we form graph $H$ . Initially, $G_1$ and $G_2$ each have perfect matchings of size 4 (matching all vertices in both partitions). In their disjoint union, you could achieve a total matching of 8 edges by using both perfect matchings simultaneously, since the graphs share no vertices. Now we add one edge between $Y_1$ and $X_2$ . This creates a single connected component, but critically, it doesn't increase the maximum matching size. Here's why: $H$ now has 8 vertices that could potentially be matched from the "left" side ( $X_1 \cup Y_1$ ) and 8 vertices on the "right" side ( $Y_2 \cup X_2$ ). However, any maximum matching can still use at most 8 edges total, achieving perfect matching of all 16 vertices. Option A is wrong because adding one edge between partitions doesn't disrupt the bipartite structure - $H$ remains bipartite with partitions $(X_1 \cup Y_1)$ and $(X_2 \cup Y_2)$ . Option B is incorrect because 9 edges would require 18 vertices, but we only have 16. Option C fails for the same reason - we cannot exceed 8 edges with 16 vertices. Study tip: In matching problems, always count vertices in each partition first. The maximum matching size cannot exceed half the total vertices in any bipartite graph.
A bipartite graph $G$ with bipartition $(A, B)$ has the property that for every subset $S \subseteq A$ with $|S| \leq 3$ , we have $|N(S)| \geq |S|$ . However, there exists a subset $T \subseteq A$ with $|T| = 4$ such that $|N(T)| = 3$ . If $|A| = 6$ and $|B| = 6$ , what is the maximum possible size of a matching in $G$ ?
Answer: 5 By Hall's theorem, since there exists $T \subseteq A$ with $|T| = 4$ and $|N(T)| = 3 < 4$ , there is no matching that saturates all of $A$ . However, we can still find a large matching. The bottleneck is the 4-subset $T$ that can reach only 3 vertices in $B$ . At most 3 vertices from $T$ can be matched. The remaining $6 - 4 = 2$ vertices in $A \setminus T$ could potentially be matched to vertices in $B \setminus N(T)$ . Since $|B \setminus N(T)| = 6 - 3 = 3 \geq 2$ , we can match these 2 vertices as well, giving a total matching size of $3 + 2 = 5$ . Choice A severely underestimates. Choice B (4) doesn't account for matching vertices outside $T$ . Choice D (6) ignores the Hall condition violation.
Consider a complete bipartite graph $K_{3,4}$ with vertex sets $A = \{a_1, a_2, a_3\}$ and $B = \{b_1, b_2, b_3, b_4\}$ . How many different maximum matchings does this graph have?
Answer: 24 In $K_{3,4}$ , the maximum matching size is $\min(3,4) = 3$ , so we need to match all 3 vertices from set $A$ to 3 of the 4 vertices in set $B$ . First, choose which 3 vertices from $B$ to use: $\binom{4}{3} = 4$ ways. Then, for each choice, arrange the 3 vertices from $A$ to match with the chosen 3 vertices from $B$ : $3! = 6$ ways. Total: $4 \times 6 = 24$ maximum matchings. Choice A (12) might result from incorrectly calculating $\binom{4}{3} \times 3 = 12$ . Choice C (36) could come from incorrect overcounting. Choice D is wrong because the structure of $K_{3,4}$ determines the count regardless of labeling.
Consider a bipartite graph $G = (X \cup Y, E)$ where $|X| = 5$ and $|Y| = 4$ . Every vertex in $X$ has degree 3, and every vertex in $Y$ has degree at least 2. Which statement about maximum matchings in $G$ is necessarily true?
Answer: The maximum matching has exactly 4 edges and saturates all vertices in $Y$ Since $|Y| = 4$ and we're looking at a bipartite graph, the maximum possible matching size is $\min(|X|, |Y|) = \min(5, 4) = 4$ . The degree conditions ensure sufficient connectivity: total degree from $X$ is $5 \times 3 = 15$ , and since every vertex in $Y$ has degree at least 2, there are enough edges for a complete matching of $Y$ . By König's theorem and Hall's theorem, these degree conditions guarantee that all vertices in $Y$ can be matched. Choice B underestimates the matching size. Choice C is impossible since $|Y| = 4$ limits us to at most 4 edges. Choice D is incorrect because the degree constraints are sufficient to guarantee the maximum.
A graph $G$ has vertex set $V = \{a, b, c, d, e, f\}$ and edge set $E = \{(a,d), (a,e), (b,d), (b,f), (c,e), (c,f)\}$ . If $G$ is bipartite with bipartition $(X, Y)$ , what is the size of the maximum matching in $G$ ?
Answer: 3 First, we verify the graph is bipartite by finding a valid bipartition. Setting $X = \{a, b, c\}$ and $Y = \{d, e, f\}$ works since all edges connect vertices from different sets. To find the maximum matching, we can use the fact that in a bipartite graph, we want to match as many vertices as possible. We can match: $(a,d)$ , $(b,f)$ , and $(c,e)$ , giving us 3 edges. This is maximum because we have 3 vertices in each partition, and we've successfully matched all of them. Choice A (2) represents finding only a partial matching. Choice C (4) is impossible since we only have 6 vertices total. Choice D is incorrect because the bipartition shown is valid.

Start this quiz