-1
$\begingroup$

Good Evening,

So I am trying to solve this exercise which is a paticular case of maximum flow algorithm. Here the graph must have all even edges and 1 odd edge and it must have a maximum flow that is odd.

Now I need to prove the following two points which state that the single odd edge must have a flow $>1$ and/or that edge must have maximum flow in it with respect to its capacity.

I understand that running certain algorithms to find odd flow in such cases prove that both statements are correct that is there is a flow $>1$ in odd edge and also there is maximum flow always in that odd edge. But I don't know how to prove it formally.

Question text:

Consider a graph $G=(V,E)$, with integer capacities on the edges, such that for all $e\in E\setminus\{e^∗\}$, it holds that $c_e$ is an even number, and $c_{e^∗}$ is odd. Suppose that there is a maximum flow in this graph with odd flow.

a. Prove/Disprove: It must be that in every maximum flow, there is a flow in $e^∗$ (i.e., $f_{e^∗}>0$).

b. Prove/Disprove: It must be that in every maximum flow, there is a full flow in $e^∗$ (i.e.,$f_{e^∗}=c_{e^∗}$).

enter image description here

$\endgroup$
2
  • $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics. You can use LaTeX. Don't forget to give proper attribution to your sources! $\endgroup$
    – Nathaniel
    Nov 26, 2022 at 13:07
  • 1
    $\begingroup$ I am sorry, I have added the question in text as well. $\endgroup$
    – ConScience
    Nov 26, 2022 at 13:19

1 Answer 1

0
$\begingroup$

The Max-flow/Min-cut theorem can be used to prove this property.

As a reminder, $f$ is a max-flow if and only if there exists a cut $X$ of capacity $|f|$.

Let $f$ be a max-flow of odd value in $G$.

a. Suppose there is no flow through $e^*$. Then in $G[V\setminus\{e^*\}]$, $f$ is still a max-flow. However, since all edges have even capacity, all cuts have even capacity. Contradiction.

b. The same idea can be used, I will let you try to find the details.

$\endgroup$
1
  • $\begingroup$ So what I can understand and by running some example network flows., is that the cut must have a one edge as odd capacity. and since there will be odd capacity in the cut, the max flow will be odd since cut flow = max flow. and because odd edge will be one of the edges of the cut, it will have the max flow itself. Is that correct? $\endgroup$
    – ConScience
    Nov 26, 2022 at 18:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.