Gráfico con $n$ nodos y $2n$ flechas

Question

Dejemos que $G$ sea un grafo dirigido en $n$ nodos tales que:

1. Cada nodo tiene al menos una flecha que entra en él

2. Cada nodo tiene precisamente dos flechas que salen de él.

3. Entre dos nodos hay una flecha como máximo en una dirección.

En estas condiciones, ¿es cierto que existe un camino entre dos nodos cualesquiera de G? Si es así, ¿cómo se demuestra?

(Quiero agradecer al Sr. Farin y a Barry por ayudar a aclarar mi pregunta; la anterior es aquí .)

Answer 1

No es cierto.

Por ejemplo, en lo que sigue, no hay camino desde el pentágono de la derecha al de la izquierda.

Añadido: Quizás un ejemplo más sencillo

Answer 2

Aunque Henry proporcionó algunos contraejemplos fácilmente verificables, yo acepté el reto y traté de encontrar uno con el mínimo número de nodos. Creo que es ocho, como se ejemplifica en:

Cualquier sección inalcanzable necesitará al menos tres nodos, debido a la primera regla. El criterio de distinción de las flechas salientes y entrantes prohíbe un gráfico con cuatro nodos que satisfagan las reglas, por lo que necesitamos cinco nodos adicionales para completar el trabajo.