# What was the name of that generalization of “Hall's marriage theorem”?

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.

-

According to a Google search, the "Ore-Ryser f-factor theorem" gives necessary and sufficient conditions for there to be such a subgraph.

-

Are you refering to the Tutte theorem?

http://en.wikipedia.org/wiki/Tutte_theorem

In the mathematical discipline of graph theory the Tutte theorem, named after William Thomas Tutte, is a characterization of graphs with perfect matchings. It is a generalization of the marriage theorem and is a special case of the Tutte-Berge formula.

-
I don't think so. Tutte's theorem generalizes the marriage theorem to non-bipartite graphs, but still constructs ordinary perfect matchings (i.e. 1-reguluar subgraphs). However, the result that is being asked for here still has a bipartite input and instead generalizes the required output from an 1-regular graph to something with specified node degrees. – Henning Makholm Jun 23 '12 at 16:22
There is also the "Tutte f-factor theorem", which allows specified degrees AND non-bipartite graphs. – Colin McQuillan Aug 1 '12 at 15:38