Maximal flow and minimal cut in complete graphs

Question

The question is as follows:

We define on the complete graph $K_n$ with the vertices {$v_1, v_2, ... , v_n$} the following directions: for every j>i, the edge $v_i v_j$ is directed from $v_i$ to $v_j$ if |i-j| is odd, and from $v_j$ to $v_i$ if |i-j| is even. We define the capacity function c($v_i v_j$)=|i-j|, and set $v_1$ as the source and $v_n$ as the sink. Find a maximum flow and a minimum cut.

Obviously the idea is to use the Max-flow Min-cut Theorem. However, I encounter few difficulties when trying to imply it, and I fear it is mostly because of lack of understanding. My idea of solution started with computing $val(f)$ (the value of the flow). Each edge connected to the sink n will thus be negetive if it comes out of it, and positive if it comes into it. So I get:

$val(f)=\sum_{x=1}^{n-1}(-1)^{n-x+1}*(n-x)=\frac{1}{4}(2*(-1)^n*n-(-1)^n+1)$

But then, if n is odd I get that the value is negetive. Am I doing the summation wrong? How can I even find a fitting source-sink cut for a negetive value of the flow? Is it even possible? And when n is even, I get $n/2$. It's still hard to find a fitting source-sink cut with the same capacity, at least I can't think of a method to do so.

Any hints/corrections/ideas will be extremely appreciated.

Update: I managed to find the solution for odd $n$. I defined the following flow: for every $1<x<n$, where x is even, I allow the flow from x to n to be on full capacity (and none out of n). Furthermore, I add a flow from 1 to each such x on full capacity. Lastly, I add a flow between every x and (n-x+1) (which will go in the direction of the lesser one), at full capacity too. I then show that the flow I described is feasible as it holds the conservation constraints for each x (the odd vertices besides 1 and n have no flow coming from them or into them, all set to 0). Once that's done, it's obvious that the capacity of cutting all the vertices besides n is the same as the val(f) of this flow, and therefore it's a maximal flow and minimal cut. The value according to the summation is $\frac{1}{4}(n-1)^2$.

I still struggle with even n. I can see that for every n I checked (up to 10), there was a feasible flow where all the odd vertices gave their full capacity into n (and none out of it of course). However, each required many additional paths to make it feasible. There is a certain pattern to these paths, yet I can't find it. I will extremely appreciate if anyone can guide me to the pattern these paths follow that allow such a flow to be feasible.

Answer 1

It seems I managed to solve it.

We split the case for even n, and odd n. The idea in general is to show that in both cases, there is a feasible flow where every edge directed to n flows with full capacity, while none comes out of n. If such a flow is feasible, it's obviously a maximum flow and a minimum cut of same value (beyond how intutive it is that the flow is maximum in that case, the flow would have the same value as the cut of all the vertices besides n, and therefore we have a minimum cut and maximum flow.

Odd n:

We set all the even vertices to go to $n$, at full capacity. We set $1$ to go to all the even vertices at full capacity. We set a full capacity flow between each even vertex $x$, and another even vertex $n-x+1$. All other flows are set to zero. As we can see no odd vertex between 1 and n has been affected, so we just have to ensure that for every even vertex $x, 1<x<n$, $f^+(v)-f^-(v)=0$. And inded: $+(n-x)-(x-1)-(n-x+1-x)=0$. Therefore this flow is feasible.

In this case $val(f)=cap(S,T)=\sum_{x=1}^{\frac{n-1}{2}}(n-2x)=\frac14(n-1)^2$

Even n:

Here it gets slightly more complicated. We define all odd vertices $x, 1<x<n$ to flow to $n$ at full capacity. Then, $1$ also flows at full capacity to each $x-1, 1<x-1<n$ (when $x-1$ is obviously even). In turn, $x-1$ flows at full capacity to $x$, and at the remaining capacity to $2$, which in turns flows again with same remaining capacity to $x$, which then distributes this capacity to two for each $x-2i, 1<x-2i<x$. In this case we will once again get that $f^+(v)-f^-(v)=0$ And therefore the flow is feasible.

In this case $val(f)=cap(S,T)=\sum_{x=1}^{\frac{n}{2}}(n-(2x-1))=\frac{n^2}{4}$.