When is a worker-to-shift graph bipartite by construction, and when must you actually test it?

## Two graphs that look alike and are not Almost every scheduling story can be drawn as a graph, but the drawings fall into two structurally different families, and a senior candidate is expected to name which one they are in before reaching for an algorithm. **Family 1 — bipartite by construction.** The vertices come from two distinct entity types and an edge always spans the types. Workers and shifts, with an edge meaning eligibility. Applicants and roles. Devices and slots. The two sides are given by the domain, not discovered: it is impossible, in a correct build, for an edge to join two workers, because an edge *means* an eligibility relation between one worker and one shift. Here the two-coloring sweep is not wrong, it is simply redundant — it will always answer yes, and that yes carries no information you did not already have. **Family 2 — bipartiteness is a hypothesis.** The vertices are peers of one type and the edge is a relation among them: "these two people must not be on the same shift", "these two vendors must not share a table", "these two jobs must not run on the same host". Now there is nothing forcing a two-way split to exist. Whether the population can be divided into two groups is exactly the bipartiteness question, and the answer is often no. Running the check is the whole job, and its failure is not a defect — it is a finding about the data. ## What to do in family 1 instead of checking Since the property is guaranteed by the model, the useful engineering is to make sure the model is what actually got built: - **Keep the sides explicit.** Store the two vertex sets separately, or carry a type tag on each vertex, rather than reconstructing the split later by guessing from ids. - **Do not let the id spaces collide.** The classic production failure is worker id 7 and shift id 7 mapping to the same vertex index. The graph silently gains an edge that joins two workers, or worse, fuses a worker and a shift into one vertex. Nothing crashes; the assignment just comes out wrong. - **Assert at the boundary.** If you want a runtime guard, assert on ingest that every edge has one endpoint of each type. That is an `O(E)` scan and it fails loudly at the offending row, which is far more actionable than a two-coloring clash discovered three stages downstream. - **Keep the coloring sweep in your pocket for forensics.** If an assignment does come out nonsensical and you suspect a build bug, running the two-coloring over the constructed graph and printing the odd cycle names the rows that broke the typing. That is the one time the check earns its keep in family 1. ## What to do in family 2 Run the check per component, and treat both outcomes as deliverables: - **Yes**: the coloring *is* the answer — the two groups, ready to hand over. If the downstream step is a matching between those groups, you have now legitimately manufactured a family-1 graph out of a family-2 one. - **No**: report the odd cycle, not just the boolean. "These five people are mutually constrained in a ring, so no two-way split exists" is something an operations owner can act on; "infeasible" is not. Expect the follow-up question of what to do next, and be honest that removing one conflict from one odd cycle may leave other odd cycles behind, so it is an iterative negotiation rather than a one-step repair. ## Why the modeling call changes the algorithm This is the part that makes the distinction more than pedantry. Matching algorithms written for bipartite graphs rely on the two-sided structure — they grow alternating paths from one side and the structure guarantees those paths behave. Feed such a routine a graph with same-side edges and you do not get a clean rejection; you get output whose optimality guarantee simply does not hold. Maximum matching on a *general* graph is a genuinely different and heavier algorithm — the blossom construction exists precisely to handle the odd cycles that bipartite graphs cannot contain. So "is this bipartite?" is not a validation step bolted on before the real work; it decides which family of algorithm the problem belongs to. ## And a boundary worth stating Bipartiteness is a **precondition** for bipartite matching, never a guarantee that a satisfying assignment exists. A graph can be perfectly bipartite and still have no way to give every worker a shift — if six workers are all eligible only for the same two shifts, the structure is fine and the assignment is impossible. Existence of a complete assignment is governed by a separate condition on how many distinct neighbours each subset of one side has. Candidates who conflate the two answer "yes, it's bipartite" to a question that was really about feasibility.