Skip to main content
1 of 2
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

Menger theorem via matroids

Let $G=(V,E)$ be oriented graph, $Y\subset V$ be some fixed set of its vertices. Call $A\subset V$ independent if there exist $|A|$ vertex-disjoint pathes strating in $A$ and ending in $Y$. It is not hard to prove this independence system is actually matroid. (I saw this example in some Russian book, but it should be well known.)

Menger's theorem (in Goering's form, I think) states that rank function of this matroid is given by

$r(A)=$the minimum number vertices which may be deleted so that no path from $A$ to $Y$ remains.

Is there any matroid interpretation, or matroids-assisted proof of this?

I saw some papers in which both Menger theorem and matroids appear in the title, but on the first glance they deal with usual cycles/cuts grtaph matroids.

Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459