Teorema del flujo máximo-mínimo, por qué la falta de una ruta de aumento implica la existencia de un flujo máximo.

Question

La prueba se toma del curso Algoritmo II, Princeton, coursera. En la prueba de iii => i, ¿Por qué/Cómo iii implica la existencia del corte (A, B)?

Answer 1

$A$ se define simplemente como el subconjunto de vértices que cumplen la propiedad establecida. Así que no hay nada que probar al respecto: simplemente existe. Potencialmente podría ser el conjunto vacío, pero eso (junto con su complemento $V(G)$) aún se consideraría un corte. Dicho esto, no está vacío aquí ya que los caminos de longitud $0$ cuentan, y así que siempre tendrás al menos a $s\in A$