1
$\begingroup$

How would you prove that the number of cuts in a graph (where cut is a set of edges which split two vertices) cannot be smaller than the number of directed paths from one vertex to the other?

1 Answers 1

1

That would depend on what you know about graphs. Do you know the Max-Flow-Min-Cut theorem?

  • 1
    @Ondrej: They are if you assign each edge a capacity of $1$. Specifically, you want to look at [Menger’s theorem](http://en.wikipedia.org/wiki/Menger%27s_Theorem); you may find the last two PDF’s listed under *External links* useful.2019-05-17