0
$\begingroup$

According to my notes;

• Theorem (Hall's Theorem) – If G is a bipartite graph, and for any 𝐴 ⊆ 𝑋 and any 𝐵 ⊆ 𝑌, and we have |𝐴| ≤ |𝑁(𝐴)| and |𝐵| ≤ |𝑁(𝐵)| , then there is a perfect matching of G.

enter image description here

I have attached the work that I did using that theorem and it shows that there is a perfect matching, however my friend said that this bipartite graph actually has no perfect matching so can someone explain to me how to use halls theorem correctly?

In set A the number of neighbors is 4 and the set B there are 5 neighbors ?

EDIT: I found the following definition of a perfect matching with bipartite graphs online and it says

When there are an equal number of nodes on each side of a bipartite graph, a perfect matching is an assignment of nodes on the left to nodes on the right, in such a way that

I) each node is connected by an edge to the node it is assigned to, and

II) no two nodes on the left are assigned to the same node on the right

Does this mean that a vertex in a perfect matching on the left side can point to two vertices on the right side?

$\endgroup$
1
  • $\begingroup$ A matching is a collection of disjoint edges. A prefect matching is a connection of disjoint edges such that every vertex is in one edge in the collection. $\endgroup$ Dec 9, 2015 at 23:38

1 Answer 1

0
$\begingroup$

No, the graph in your picture does not have a perfect matching. See where the theorem says "for any $A\subseteq X$ and any $B\subseteq Y$"? What is $N(A)$ if $A$ is the top four vertices on the left? What is $N(B)$ if $B$ is the bottom two elements on the right? (By the way, it would be easier to write this answer if you had labeled the nodes in the diagram.)

That so-called "definition" that you found on-line is stated confusingly and does not seem to be quite right. Please give the link.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.