To Proof:

Let $G = (V,E)$ be an infinite bipartite graph with $V = S \overset{.}{\cup}T$ and finite node degree for each node.

G has a matching, that covers a set S iff for all subset $H \subseteq S: |N(H)| \geq |H| $ where $N(H)= \{x \in V \mid \exists y \in H \text{ that } \{x,y\} \in E\}$

This is hall's theorem with only difference of infiniteness of the bipartite graph.

How can I proof this by using Compactness theorem and Hall's theorem?

  • $\begingroup$ What have you tried? Do you know how topology comes to the picture? And which topology to use? $\endgroup$ – Blackbird Apr 22 at 12:45

Your Answer

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

Browse other questions tagged or ask your own question.