The Matching Problem

Graph Theory · Axiom Academy

Discover the concept of matchings through interactive graph exploration. Learn how to pair vertices without conflicts! Let's start with a simple graph. Click on two vertices to create an edge between them. Try connecting some vertices! Click on edges to select them. Watch what happens when you try to create a matching! Can you tell which of these is a valid matching? The left shows a valid matching , and the right shows an invalid one . Middle vertex touches 2 edges! Matchings appear everywhere! Here are some real-world scenarios where matching problems are critical. You have 5 employees and 5 tasks. Each employee can do certain tasks. How do you assign one task per employee so everyone works on something they can do? This is a matching problem - pairing employees to tasks with no overlaps. The classic "stable marriage problem" pairs people based on preferences. Each person marries at most one other person - a perfect matching! This algorithm is used in medical residency matching and school admissions. Assigning students to dorm rooms, or tenants to apartments. Each person gets one room, each room gets one person (or pair). The matching ensures fair, conflict-free assignments. In computer networks, matchings help route data packets through switches. Each port can handle one connection at a time - a matching ensures no conflicts and maximum throughput. A maximum matching is a matching with the most edges possible. Can you find one in this graph?

This is the written version of the interactive lesson above. See the full Graph Theory course.