A Hoffman-tétel azt mondja ki, hogy mikor van adott kapacitásokra egy irányított gráfban megengedett áram.

Jelölje ${\displaystyle \delta _{x}(S)}$ az x szerinti S-be menő beáramlást, ${\displaystyle \rho _{x}(S)}$ az S-ből való kiáramlást. A D=(V,A) irányított gráfban akkor és csak akkor van megengedett áram, ha ${\displaystyle \rho _{f}(X)\leq \delta _{g}(X)}$ minden ${\displaystyle X\subset V}$ halmazra.

Ha emellett a korlátok még egész értékűek is, akkor van egész értékű megengedett áram.

A szükségességet egyszerű igazolni:

${\displaystyle \rho _{f}(X)\leq \rho _{x}(X)=\delta _{x}(X)\leq \delta _{g}(X)}$, amiből a feltétel következik.

Az elegendőséghez vezessük be a ${\displaystyle \gamma (x)=\delta _{g}(X)-\rho _{f}(X)}$ függvényt. A feltétel most ekvivalens azzal, hogy ${\displaystyle \gamma (x)\geq 0}$. Jelölje ${\displaystyle d_{x}}$ az x(e) értékek összegét az X\Y és az Y\X között menő élekre.

Lemma: ${\displaystyle \gamma (X)+\gamma (Y)=\gamma (X\cap Y)+\gamma (X\cup Y)+d_{g-f}(X,Y)}$

Lemma bizonyítása: minden lehetséges élre le kell ellenőrizni, hogy valóban mindkét oldalhoz ugyanannyival járul hozzá.

Visszatérve a tételhez legyen egy e él pontos, ha f(e)=g(e), és Z pontos halmaz, ha γ(Z)=0.

Tegyük fel indirekt, hogy a Hoffman-feltétel nem szükséges. Ekkor vannak ellenpéldák valamely D irányított gráfon. Most rögzítsük D-t. Tekintsünk egy olyan ellenpéldát D-n, amiben a pontos élek és halmazok együttes száma maximális az ellenpéldák között.

Ha minden él pontos lenne, akkor a feltétel szerint f és g közös értéke megengedett áram lenne. Legyen a egy nem pontos él, így f(a)<g(a). Állítjuk, két pontos halmazt köt össze.

Ha ugyanis nem lépne be egy pontos T halmazba, akkor f(a)-t meg lehetne növelni egészen addig, amíg vagy a válna pontossá, vagy egy halmaz, amibe belép, és továbbra is teljesül:${\displaystyle \rho _{f}(X)\leq \delta _{g}(X)}$

Ez már nem ellenpélda, ezért van rajta megengedett áram, ami az eredetin is megengedett.

Hasonlóan bizonyítható, hogy kilép egy pontos S halmazból.

a létezése miatt ${\displaystyle d_{g-f}(S,T)>0}$, ezért a lemma szerint ${\displaystyle 0+0=\gamma (S)+\gamma (T)>\gamma (S\cap T)+\gamma (S\cup T)\geq 0+0}$, ellentmondás.

Ugyanezzel a gondolatmenettel adódik az egész értékű eset.

A szükségesség igazolása egyszerű, így itt csak az elegendőségről lesz szó.

Tekintsük a ${\displaystyle Qx\leq 0}$, ${\displaystyle x\leq g}$, ${\displaystyle -x\leq -f}$ rendszert. Ez éppen a megengedett áramokat írja le.

Ha nincs megengedett áram, akkor a Farkas-lemma miatt van egy (y,u,v) 0 és 1 értékű vektor, amelyre

1. yA+u-v=0

és 2. ug-vf<0.

${\displaystyle f\leq g}$, ezért minden élre feltehető, hogy u(e) és v(e) valamelyike nulla. Legyen Z azon pontok halmaza, ahol y(Z)=1. Ekkor 1. miatt minden élre, ami Z-ben, vagy V\Z-ben van, u(e)=v(e)=0, továbbá minden Z-be lépő e élre v(e)=1 u(e)=0, és minden Z-ből kilépő e élre v(e)=0 u(e)=1

Mivel ${\displaystyle ug=\delta _{g}(Z)}$ és ${\displaystyle vf=\rho _{f}(Z)}$, azért 2. ellentmond a feltételeknek.

• http://www.cs.elte.hu/~frank/jegyzet/opkut/ulin.2008.pdf