Translating Selection Problems Into Bipartite Graphs

From Choices to Edges

Suppose a collection of people each has a set of acceptable options, and we want to assign one option to each person without using any option twice. The restrictions are local—each person has their own set of permissible choices—but the requirement that choices be distinct links the decisions together. A bipartite graph records both parts of this problem: one side records who needs a choice, and the other records the available choices. An edge records permission to make a particular choice.

We will use a finite indexed family \((A_i)_{i\in I}\) of sets, together with a finite set \(X\) such that \(A_i\subseteq X\) for every \(i\in I\). The indices matter: if \(A_i=A_j\) but \(i\ne j\), these are still two separate choice requirements. Requiring \(X\) to be finite ensures that the graph constructed below is finite. In particular, taking \(X=\bigcup_{i\in I}A_i\) is a finite-universe construction when \(I\) is finite and every \(A_i\) is finite. If some \(A_i\) is infinite, that union need not be finite, so a graph built with it need not be finite.

To translate the problem, make one vertex \(i_L\) for each index \(i\in I\), and one vertex \(x_R\) for each possible representative \(x\in X\). The subscripts distinguish the two classes, even if an index and an element happen to have the same name. Join \(i_L\) to \(x_R\) exactly when \(x\in A_i\). This is a finite simple bipartite graph: every edge goes between the two classes, and each permitted pair gives just one edge.

An edge says a choice is allowed, not that it has already been made. A matching selects allowed pairs while preventing repeated indices and repeated representatives. To represent every set, the matching must saturate all of \(L\). It does not have to saturate all of \(R\): if there are more possible representatives than sets, some right-side vertices can remain unused. A matching saturating both classes is called a perfect matching; it is the right requirement only when every vertex on both sides must be matched.

The Exact Correspondence

Proof. Suppose first that \((x_i)_{i\in I}\) is a system of distinct representatives. Since \(x_i\in A_i\), the edge \(i_Lx_{i,R}\) belongs to \(E\) for every \(i\). Take the set of these edges. No two share a left endpoint because they correspond to different indices. No two share a right endpoint because the representatives are distinct. They therefore form a matching, and each vertex of \(L\) is incident with its corresponding edge, so the matching saturates \(L\).

Conversely, suppose \(M\) is a matching saturating \(L\). For each \(i\in I\), exactly one edge of \(M\) is incident with \(i_L\): at least one exists by saturation, and at most one exists because \(M\) is a matching. Write that edge as \(i_Lx_{i,R}\). The definition of \(E\) gives \(x_i\in A_i\). If \(i\ne j\), the two edges incident with \(i_L\) and \(j_L\) cannot share a right endpoint, again because \(M\) is a matching. Thus \(x_i\ne x_j\), and the choices form a system of distinct representatives. \(\square\)

This correspondence also applies when only some of the sets are to receive representatives. A partial system of \(k\) distinct representatives means choosing \(k\) distinct indices and one allowed, distinct representative for each chosen index. The selected indices are precisely the left endpoints of the corresponding matching edges.

Proof. Given a partial system, include the edge \(i_Lx_R\) for each selected index \(i\) and its representative \(x\). The choices are allowed, so these are edges; distinct selected indices and distinct representatives ensure that no two edges share an endpoint. There are \(k\) chosen indices, so this is a matching of size \(k\). In the reverse direction, a matching of size \(k\) has \(k\) distinct left endpoints and \(k\) distinct right endpoints. Each of its edges \(i_Lx_R\) certifies that \(x\in A_i\). Assigning each such \(x\) to its index gives a partial system of \(k\) distinct representatives. For \(k=0\), both sides are the empty selection and the empty matching, so the statement also holds in that case. \(\square\)

Worked Translations

Modeling Choices and Common Pitfalls

The graph is only as accurate as the choices used to build it. Each left vertex must represent one requirement that needs its own choice. Each right vertex must represent one distinguishable resource or option. Include an edge exactly when that option is permitted for that requirement. If two resources have the same description but are independently available, they need separate right-side vertices; identifying them would falsely force them to count as the same representative. Conversely, adding an edge for a forbidden choice could create a matching that does not solve the original problem.

Common mistake: allowing a repeated representative. In the second example, the edges \(p_Lu_R\) and \(q_Lu_R\) both exist. It is incorrect to select both and call them a matching of size \(2\): they share the endpoint \(u_R\). The corrected selection must use distinct right endpoints. Since both \(p\) and \(q\) can use only \(u\), at most one of them can be matched, and the largest matching has size \(2\) after also matching \(r\) to \(v\).

Common mistake: assuming the union is finite. A finite index set does not by itself make \(\bigcup_{i\in I}A_i\) finite. For example, if \(I=\{1\}\) and \(A_1\) is the set of natural numbers, the union is infinite. To use the finite-graph formulation here, specify a finite universe \(X\) containing every \(A_i\); taking the union as \(X\) is valid when the family consists of finitely many finite sets.

The translation does not itself decide whether a saturating matching exists. It identifies the exact graph question that must be answered. Results about matchings can then be applied to that graph, while the correspondence proved above guarantees that a matching solution translates back to valid choices. The distinction between saturating \(L\) and finding a perfect matching is important whenever the numbers of requirements and possible representatives differ.