25.1.3. Definition of Matching

Try these first

1. 1.

   Define a bipartite graph.

   Hint

   Think about how the groups are structured.

2. 2.

   What is a maximum matching?

   Hint

   Consider which matching has the most connections.

3. 3.

   What defines a maximum matching?

   • It has the fewest edges
   • It has more edges than maximal matching
   • It has the largest number of edges

   Hint

   Think about which matching allows the most connections.

4. 4.

   True or False: In a maximal matching, you can add more edges without losing its properties.

   • True
   • False

   Hint

   What happens if you try to add edges?

5. 5.

   Given a bipartite graph with 4 tasks and 3 employees, can you find a complete matching? Justify your answer.

   Hint

   Count how many tasks can be paired with available employees.

6. 6.

   Create a scenario with three students and three projects where not all students are assigned a project. Analyze if a maximal matching exists.

   Hint

   Consider how edges connect.