# Max flow in bipartite network where all vertices on the left hand side have degree exactly $2$

I have a flow question which I'm stumped on but seems like there should be an answer that I am not seeing.

Consider a network with a start $$s$$ and an end $$t$$ and a bipartite graph $$L \cup R$$. $$s$$ is connected to all vertices in $$L$$ via edges with capacity $$1$$. All vertices in $$R$$ are connected to $$t$$ via edges with capacity $$C$$ where the only constraint on $$C$$ is that it's non-negative where $$C> 0$$. All vertices in $$L$$ are connected to exactly two vertices in $$R$$ via edges with capacity $$\infty$$. I want to check if there is a max flow of size $$|L| = degree(s)$$. I don't want to find the max flow if such a flow does not exist; I just want to check whether the max flow has this size.

Even if this is solvable for larger $$C$$ and not constant $$C$$ such as $$C = \text{poly}\log n$$, this would still be quite useful to me.

Can I do this in linear or near-linear $$O(n \cdot polylog(n))$$ time? It seems like it may be plausible. If so, I'd greatly appreciate knowing the algorithm.

• Yes you're correct, if the graph was two regular, then we can verify using an Euler Tour but this is not a two regular graph. So it may not be simple to even get a perfect matching. My original question still stands though. Sep 12, 2022 at 2:08