Ejercicio 3 · Matemática Discreta UAB Juny 2022

a. Justifica que, si un grafo bipartito completo $K_{m,n}$ es euleriano, entonces su número de aristas es necesariamente múltiplo de 4.

Solución: Un grafo conexo es euleriano si y solo si todos sus vértices tienen grado par. En $K_{m,n}$, los $m$ vértices tienen grado $n$ y los $n$ vértices tienen grado $m$. Por tanto, tanto $m$ como $n$ deben ser pares ($m = 2p$, $n = 2q$). Así, $|E| = m \cdot n = (2p)(2q) = 4pq$, que es múltiplo de 4.

¿Puede ser hamiltoniano?

Solución: No

b. Justificación con el teorema de Grinberg...

Solución: Aplicando el teorema de Grinberg, $\sum_{i\ge 3}(i-2)(f_i' - f_i'') = 1\cdot(f_3' - f_3'') + 2\cdot(f_4' - f_4'') + 6\cdot(f_8' - f_8'') = 0$. Como $f_3' + f_3'' = 7$, la diferencia $f_3' - f_3''$ es impar, mientras que los otros términos son pares. La suma resulta Impar + Par + Par = Impar $\ne 0$, por lo que el grafo no puede ser hamiltoniano.