Lesson 2

For example, here are three edge-disjoint paths: \[1 \to 2 \to 5 \to 0, \ 1 \to 4 \to 8 \to 0, \ 1 \to 3 \to 4 \to 6 \to 7 \to 0 \ .\]

At the same time, four edges go out from vertex 1 and four edges go into vertex 0. Could there be four edge-disjoint paths from 1 to 0? If not, how can we be sure?