Discrete Math Quiz: Bipartite Graphs And Matchings

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$?

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?

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?

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$?

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?

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$?

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'$?

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$?

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?

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$?

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$?

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$?

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$?

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?

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?