Greedoids from flames

A digraph D with r ∈ V ( D ) is an r ‐flame if for every v ∈ V ( D ) − r , the in‐degree of v is equal to the local edge‐connectivity λ D ( r , v ) . We show that for every digraph D and r ∈ V ( D ) , the edge sets of the r ‐flame subgraphs of D form a greedoid. Our method yields a new proof of Lovász's theorem stating: for every digraph D and r ∈ V ( D ) , there is an r ‐flame subdigraph F of D such that λ F ( r , v ) = λ D ( r , v ) for v ∈ V ( D ) − r . We also give a strongly polynomial algorithm to find such an F working with a fractional generalization of Lovász's theorem.