Does Birkhoff - von Neumann imply any of the fundamental theorems in combinatorics? I recently had the occasion to think about Hall's Marriage Theorem for the first time since my undergraduate combinatorics class more than a decade ago.  Reading the wikipedia article linked above, I was interested to see that it is regarded as equivalent to several other fundamental theorems in combinatorics, for instance Dilworth's Theorem on posets of finite width and König's Theorem on matching in (finite?) graphs.  I was able to track down the proofs of these equivalences online.
However, the article also claims that Hall's Marriage Theorem is equivalent to the (König-)Birkhoff - von Neumann Theorem, which asserts that a real matrix is doubly stochastic iff it is a convex combination of permutation matrices (if you know the Minkowski-Krein-Milman theory of extreme points in convex sets, then an equivalent assertion is that the doubly stochastic matrices form a compact convex subset of $M_n(\mathbb{R})$ with extreme points precisely the permutation matrices, and since there are finitely many extreme points one has in fact a convex polytope, the Birkhoff polytope).
But the attribution here is strange: the only citation is to this series of slides by R.D. Borgersen, for which the title is "Equivalence of seven major theorems in combinatorics"...but it only shows some of the implications!  In particular, it is not shown that Birkhoff - von Neumann implies any of the theorems as above.  So now we get to the question in my title: does it?
As a secondary question, is there a nice source which treats all these theorems (maybe not Birkhoff - von Neumann, but the other five or six, depending on how you count) at once?  In particular much of the literature I've found seems to be a bit sloppy on whether the structures involved need to be finite: it seems that "some, but not all" finiteness conditions are needed for these theorems to hold and that the folkloric equivalence is understood to apply in the finite case only. Is this correct?
 A: The book you want is Reichmeider, The Equivalence of Some Combinatorial Matching Theorems. Alas, it is long out of print. 
[Added by PLC: I am taking the liberty of reproducing the MathSciNet review.  Note that it does not mention Birkhoff - von Neumann, though this is hardly conclusive.]

It is well known that various theorems concerning bipartite matchings and network flows are all "equivalent'', in the sense that any one may be deduced easily from any other. This expository work painstakingly organises and presents various proofs of these results and of the relationships. It focusses on theorems of König and Egerváry, Hall, Dilworth, Menger, Ford and Fulkerson, and Hoffman. The book deals only with the finite case, and does not consider matroids or algorithms.  (Reviewed by Colin J.H. McDiarmid)

A: It certainly implies the Koenig marriage theorem.  Given a regular bipartite graph on vertex set $U \sqcup V$, define a "modified" adjacency matrix $A = (a_{ij})$ by $a_{ij} = 1$ if element $i$ of $U$ is adjacent to element $j$ of $V$, and $a_{ij} = 0$ otherwise.  Since each row and column of $A$ adds to the degree, you can normalize it to get a doubly stochastic matrix whose nonzero entries still record adjacency in the graph.  Write this as a convex combination of permutation matrices, pick one of them, and use it as a modified adjacency matrix of a matching (since its nonzero entries must be nonzero in $A$, this is contained in the original graph).
To get the full Hall theorem, you need to check that the Hall condition is enough to do the doubly stochastic normalization, which I don't see but sounds reasonable.
EDIT: I misunderstood which Koenig theorem you meant.  Sorry!
