# Maximum Flow algorithm. How to prove the following statements

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^∗}$$).

• 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! Nov 26, 2022 at 13:07
• I am sorry, I have added the question in text as well. Nov 26, 2022 at 13:19

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.