I've been stuck on this proof from my textbook:
We are considering bipartite graphs only. A will refer to one of the bipartitions, and B will refer to the other.
Here are the relevant parts of the textbook
Firstly, why is $d_h(A) \ge 1$ if H is a minimal subgraph that satisfies the marriage condition and contains A. If we let the degree of some vertex $a$, be greater than 1, then H would not be minimal, right? Wouldn't a subgraph H, where each vertex in A, has a degree of exactly 1, still satisfy the marriage condition and be minimal?
Also, I don't really understand the conclusion they reached. It starts out by assuming that H is a minimal subgraph that satisfies the marriage condition (and no other assumptions), and from there, it ends by saying that H does not satisfy the marriage conditions. To my understanding, they just proved
If H satisfies the marriage condition then H does not satisfy the marriage condition
So there's obviously something I'm misunderstanding here. I think, they were trying to do a proof by contradiction, but usually in those kinds of proofs, the assumption that needs to be disproved is done so by use of other premises and given information. However, our only assumption here was that H satisfies the condition. We then somehow ended up with teh conclusion that it doesn't.
Sorry for the long question. I really appreciate the help.
Thanks
The outline of the proof is
Your paragraph "Firstly why is $d_H(a) \ge 1$ ..." is basically the outline of the proof. You claim that removing one of the extra edges of $a$ does not cause the marriage condition to be violated, which is exactly what they show, except they do it by contradiction; that is, they show that if removing an extra edge of $a$ violates the marriage condition, then there is a contradiction.