Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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

share|cite|improve this answer

Are you refering to the 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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.