Question

I have a question that if i have a graph that is bipartite but not a perfect matching how do i justify that its not a perfect matching by using halls theorem? Whats the explanation?

Answer 1

Imagine that you have 4 students looking for a job, and 4 positions available to fill. Not all students are equal — some are smarter than others. So the companies want to hire only the smartest students.

(Students are happy with any job they can get)

Bill Corki Andrei Danny Google Blizzard Apple Costco

In this diagram, a bipartite graph, the students are at the top and the companies are at the bottom. A student and a company is connected if the company wants to hire the student. For example, Costco will hire any student, so Costco is connected to Andrei, Bill, Corki, and Danny.

Hall’s Theorem tells us when we can have the perfect matching:

Suppose is a bipartite graph with bipartition
(A, B
. There is a matching that covers if and only if for every subset
XC A
,
N(X X
where
N(X
is the number of neighbors of .

If you look closely at the diagram, you’ll notice that it doesn’t quite work:

Andrei Bill Danny Corki Google Apple Costco Blizzard

Both Blizzard and Google want to hire Corki and only Corki. But Corki can only work for one company! So the whole thing collapses; the matching fails.

Let’s rewrite Hall’s condition in the context of students and jobs:

For a set of companies, denote to mean the number of students that at least one of these companies want. If
m n
for every set of companies, then a matching is possible. Otherwise, the matching fails.

Here, a set of {Blizzard, Google} consists of 2 companies, but only one student, Corki, is wanted by either company. Since 1 < 2, the matching fails.

A perfect matching is a matching in which each node has exactly one edge incident on it.

In the above example we have a graph that is bipartite but not a perfect matching.We have proved it using halls therom.