Max-Flow Min-Cut Theorem to Hall

Try the Edmonds-Karp Algorithm ; it should suffice.

Where do they talk about Hall in this? I don't get it.

You're absolutely right; there is no "Talk" there of Hall, that is a mathematic proof which is a logical equivalent to the Max-Flow Min-Cut (Ford-Fulkerson Algorithm) that demonstrates and proves Hall's theorem.

There are several such logical equivalences relevant to your query: the Edmonds-Karp theorem, as mentioned earlier, Konig's Theorem, the Konig-Egervary Theorem, Menger's Theorem, the Max-Flow-Min-Cut Theorem (Ford-Fulkerson), the Birkhoff-Von Neumann theorem, and Dilworth's Theorem, among others. Any of those theorems may be proven true independently of one another, and any may be employed to prove any of the others based on the proof of the first. The same may be done for any of those theorems through any other of them without proving the operative theorem, but merely assuming it to be true. Here is a brief article from PlanetMath.com illustrating an inductive proof of Hall's Marriage theorem, which could then be used to prove any of the other logical equivalents, which then could be used to prove any of the others, etc etc etc. That's the neat thing about Combinatorics ; the math works.

Hi there! I really appreciate all the information you've provided but it's nothing I didn't know already. It still doesn't answer my question. All I want to show is that the Maximum-Flow = Minumum-Cut Theorem implies Hall's Marriage Theorem. Now, I don't see how induction can be used to go from Max-Flow Min-Cut to Hall. I guess an outline of a proof would be much more valuable than other information which can be found easily. Thanks!

If it was easy, it wouldn't be a course assignment. You've got the tools to do what you need to do, doing it is up to you. That's school.

Well, it's not a "course assignment." I found it in a graph theory book which totally sucks. It just states stuff without proof. Anyway, I see your point. Thanks for the help anyway.

Sorry if I seemed mean there - it is relatively advanced, but very straightforward, math, and the only way to figure it out for yourself is to work it out for yourself. That's the point I was getting at.

All the tools you need to work it out are available to you, and apparently you realize that. Cool. Work it out. You don't need a computer to do it, a TI 99 or any other advanced graphing calculator will do. So will pencil and paper.