Bipartite graphs and matching
Graph theory · Mathematics
Study notes
Q: Jobs {J1,J2} and workers {W1,W2,W3}. J1 can do W1,W2; J2 can do W2. Is there a matching covering both jobs? Try: J1-W1, J2-W2 ✓ - matching of size 2 exists! Hall check: {J1,J2} neighbors {W1,W2} (2 ≥ 2 ✓); {J2} neighbors {W2} (1 ≥ 1 ✓). Both jobs assigned - perfect for the job side!