3
$\begingroup$

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.

2 Answers 2

1

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

0

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.

  • 0
    There is also the "Tutte f-factor theorem", which allows specified degrees AND non-bipartite graphs.2012-08-01