It  remains to show that f^(∗ ) is indeed a flow for N and that f^(∗ ) (N)>f(N).

 [A flow in N is an integer-valued function** f** on E(D) such that

                       0 ≤ f(a) ≤ c(a)  for every a ∈ E(D)

and  ∑(y∈N^+ (x))▒〖f(x,y)〗 = ∑(y∈N^- (x))▒〖f(y,x)〗 for every x ∈ V(D)- {s , t }

We first observe that f^(∗ ) is integer-valued since ∆ is an integer and f is integer-valued.

Further , 0 ≤ f^∗ (a) ≤ c(a) for every  a ∈ E(D).

Hence, f^(∗ ) satisfies condition (1) .        Let s and t be the source and sink of  N .

Assume, first, that D contains an f-augmenting semipath

                             Q : s =〖 u〗0, a_1, u_1, a_2, u_2,…, u(n-1), a_n, u_n = t .

Then for each i, 1≤ i ≤ n , either

               (a) a_i = (u_(i-1), u_i) and f(a_i) < c(a_i), or

               (b) a_i = (u_i, u_(i-1)) and f(a_i)> 0 .

For each i such that a_i = (u_(i-1), u_i), let ∆_i = c(a_i) – f(a_i), and for each i such that

a_i = (u_i, u_(i-1)), let ∆_i = f(a_i).

Set ∆ = min {∆_i | 1≤ i ≤ n}, so ∆ ≥ 1.Define a function f^(∗ )on E(D) by

         f^∗ (a) = {█(f(a)+∆           if a_i " = (" u_(i-1) ", " u_i ") fo" r some i, 1≤i≤n;@f(a)-∆          if a_i " =(" u_i ", " u_(i-1) ") fo" r some i, 1≤i≤n;@   f(a)                      if a∉E (Q)                                                       )┤It  remains to show that f^(∗ ) is indeed a flow for N and that f^(∗ ) (N)>f(N).

 [A flow in N is an integer-valued function** f** on E(D) such that

                       0 ≤ f(a) ≤ c(a)  for every a ∈ E(D)

and  ∑(y∈N^+ (x))▒〖f(x,y)〗 = ∑(y∈N^- (x))▒〖f(y,x)〗 for every x ∈ V(D)- {s , t }

We first observe that f^(∗ ) is integer-valued since ∆ is an integer and f is integer-valued.

Further , 0 ≤ f^∗ (a) ≤ c(a) for every  a ∈ E(D).

Hence, f^(∗ ) satisfies condition (1) .Next we show that f^(∗ ) also satisfies condition (2) .

 Let  x ∈ V(D) – { s , t } .

If x  does not lie on Q,  then f^(∗ )(x, y) = f (x,y) for all y ∈ N^+ (x)  and

 f^(∗ )(y, x) = f (y,x) for all y ∈ N^- (x) .

Since ∑(y∈N^+ (x))▒〖f(x,y)〗 = ∑(y∈N^- (x))▒〖f(y,x)〗 ,

it follows, in this case ,that  ∑(y∈N^+ (x))▒〖f^(∗ ) (x,y)〗 = ∑(y∈N^- (x))▒〖f^(∗ ) (y,x)〗 .

Hence , f^(∗ ) satisfies condition (2) for all vertices x not on Q.

Suppose that x lies on Q .

Then , x = 〖 u〗_i for some i, 1≤ i ≤ n-1.

We consider three cases. i want the continuation of this