can sombody help me in graph theory?
I just need to know the name of the generalization of Hall's marriage theorem…
the one that states that if I have a bipartite graph between set $A$ with $n$ elements and set $B$ with $n$ elements too, I can make a "sub-graph" (a graph made only by existing connections) where every node $x$ has $f(x)$ connections iff for every set $X \subseteq A$ and $Y \subseteq B$:
-
$$\sum_{a \in A}f(a)=\sum_{b \in B}f(b)$$
-
$$\sum_{x \in X}f(x) \leq \sum_{b \in B \setminus Y}f(b)+m(X,Y) $$
Where $m(X,Y)$ is the nuber of connections between $X$ and $Y$ in the existing graph.
Best Answer
According to a Google search, the "Ore-Ryser f-factor theorem" gives necessary and sufficient conditions for there to be such a subgraph.