As far as i'm aware is states that if(using 4 as n):
Set 1 has 4 vertices
Set 2 must have 4 or more vertices
And if true, a matching holds.
But if both sets have 4 vertices. It's possible for a matching not to hold. For example, in set 2: 2 difference vertices only have one edge, going to the exact save vertex in set 1.
In this case, there would be no matching. And yet the theorem still holds there should be?
Question:
E = f(1; 5); (1; 8); (2; 5); (2; 6); (2; 7); (3; 6); ; (3; 8); (4, 6); (4; 8):
s1 = {1, 2, 3, 4}
s2 = {5, 6, 7, 8}
(i) Is there a complete matching from S1 to S2? Justify your answer with the use of
Hall's Marriage Theorem.
My answer is 'no there isn't' - because the only matching from 5 is to 2. And the only matching from 7 is to 2.
But how would i explain this via halls theorem if the theorem actually holds?
Thankyou