The Langberg-Médard conjecture is a routing assertion for a finite directed graph with unit-capacity arcs, distinct sources
,
and distinct receivers 
, with no source also a receiver. Suppose that, for
each receiver separately, there are 
pairwise arc-disjoint directed paths, one from each source
to that receiver. The conjecture asserts that forgetting all arc orientations permits
simultaneous unit fractional flows from 
to 
for all 
. Each underlying undirected graph
edge has shared unit capacity in both directions (Langberg and Médard
2009).
Cai et al. (2026) proved this statement. Liu et al. (2026) independently proved the capacitated formulation. If every receiver can recover all independent source messages at the same rate by multiple multicast coding, then prescribed-pair fractional multicommodity flow is feasible at that rate in the underlying undirected network. Oppositely oriented arcs retain their capacities as parallel edges. The hypothesis requires multicast to every receiver and is stronger than feasibility of independent directed unicasts. Liu et al. (2026) report AI-generated arguments and AI-assisted mathematical verification.
