Does Birkhoff - von Neumann imply any of the fundamental theorems in combinatorics?

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)

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!