# Comparing the number of cuts and paths in graph

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?

-

@Ondrej: They are if you assign each edge a capacity of $1$. Specifically, you want to look at Menger’s theorem; you may find the last two PDF’s listed under External links useful. – Brian M. Scott Jan 4 '12 at 6:06