I have been trying to understand how a maximum average degree problem can be solved as a maximum flow problem for my optimization class from this article: https://hal.archives-ouvertes.fr/inria-00504914/document. I don't understand this bit:

"Clearly, if $H ⊆ G$ is the densest subgraph in $G$, its $|E(H)|$ edges will send a flow of $2|E(H)|$ to their $|V (H)|$ vertices, such a flow being feasible only if $z ≥\frac{2|E(H)|}{|V (H)|}$. An elementary application of the max-flow/min-cut theorem, or of Hall’s bipartite matching theorem shows that such a value for $z$ is also sufficient."

$z$ is how much a vertex in $V(G)$ can absorb.

Would anyone like to explain this section? Particularly the max-flow/min-cut theorem application.


1 Answer 1


For any edge $e$ we put an additional vertex $v_e$ on it and direct the created par of sub-edges away from it. Now we pump in exactly $2$ units of flow through that vertex. Remember that the sub-edges are directed, so all that flow has to exit through the vertices of $V$.

Now, for any subgraph $H \subset G$ the total out-flow from $V$ has to be at least $2|E(H)|$, because each $v_e$ pumps in $2$ units of flow. Thus, whatever happens, the average outflow per vertex is at least $\frac{2|E(H)|}{|V(H)|}$. In other words, if we were to bound the out-flow of all vertices $v \in V$ by $z$, then for the flow to be possible, we have to have $z \geq \frac{2|E(H)|}{|V(H)|}$. In particular that has to be satisfied even if $H$ is the densest subgraph of $G$.

On the other hand, suppose that $z = \frac{2|E(H)|}{|V(H)|}$ where $H$ is the densest subgraph of $G$. Will this be enough to make such a flow possible? To check this, we instead upperbound the outflow from $v \in V$ by $z$, construct a maximum flow given the constraints, and see if it matches the $2|E(G)|$ value.

To see that it is indeed possible to construct such a flow, make $2$ copies of each $v_e$ and $z$ copies of each $v \in V$, and use cliques $K_{2,z}$ to connect all these copies. Now, check that the Hall's condition is satisfied, i.e., for any set of vertices corresponding to edges $v_e$, its set of neighbors is exactly the set of vertices of $V$ incident to the relevant edges. Because of how we picked $z$, the set of neighbors is always big enough. The matching gives you the flow. With some more work (eg. use fractional matchings), this will be true also if $z$ is not an integer.

I hope this helps $\ddot\smile$

  • $\begingroup$ I appreciate you taking the time to answer, but I don't understand the last paragraph since I haven't done cliques. I actually haven't studied that much graph theory. $\endgroup$
    – Eva
    Mar 31, 2016 at 16:22
  • $\begingroup$ @Eva I just mean that if there is an edge between $v_e$ and some $v$, then you connect all the copies of $v_e$ to all the copies of $v$. $\endgroup$
    – dtldarek
    Mar 31, 2016 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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