25.1.4.2. Maximal Matching

Try these first

1. 1.

   Define a bipartite graph.

   Hint

   Think about how the vertices are grouped.

2. 2.

   What is a matching?

   Hint

   Consider how roles can be paired without overlap.

3. 3.

   What defines a bipartite graph?

   • Edges connect vertices in the same group
   • Vertices divided into two groups
   • All vertices are connected

   Hint

   Consider how vertices are organized.

4. 4.

   Is a maximal matching always a maximum matching?

   • True
   • False

   Hint

   Think about sizes and properties.

5. 5.

   In a bipartite graph representing 5 jobs and 3 employees, demonstrate potential matchings and assess if a complete matching can be achieved.

   Hint

   Sketch the graph to visualize options.

6. 6.

   Apply Hall's theorem to a bipartite graph with specific subsets and determine if a complete matching is feasible. Justify your conclusion.

   Hint

   Count neighbors carefully against subset sizes.