Ruta única del mensajero (grafos)

**Qué entrena:** criterio euleriano y construcción de ruta.

Un mensajero debe recorrer cada calle exactamente una vez en el siguiente mapa:

```text
A---B
|\ |

| \ |
C---D---F
\ | /
\ | /
E
```

Para evitar ambigüedad, las calles (aristas) son exactamente estas 9:

• A-B, A-C, B-C, B-D, C-D, C-E, D-E, D-F, E-F.

¿Existe un recorrido que use **todas las calles exactamente una vez**?
Si existe, indica desde qué barrio debe empezar, en cuál terminar y da una ruta válida.

1. Bto Ato Cto Bto Dto Cto Eto Dto Fto E.
2. Idea reusable: en un grafo conexo, hay camino euleriano si y solo si hay exactamente 0 o 2 vértices impares.
3. Sí existe recorrido euleriano. Debe empezar en B y terminar en E (o al revés).

[Volver al problema](#prob-ruta-mensajero-grafos)

**Respuesta:** Sí existe recorrido euleriano. Debe empezar en **B** y terminar en **E** (o al revés).

Grados de los vértices:

• $\deg(A)=2$
• $\deg(B)=3$
• $\deg(C)=4$
• $\deg(D)=4$
• $\deg(E)=3$
• $\deg(F)=2$

Solo hay dos vértices impares (B y E), luego existe camino euleriano que empieza en uno y termina en el otro.

Ruta válida:

$$
B\to A\to C\to B\to D\to C\to E\to D\to F\to E.
$$

**Idea reusable:** en un grafo conexo, hay camino euleriano si y solo si hay exactamente 0 o 2 vértices impares.

---