Supongamos que el grado máximo de un grafo es menor o igual a 2, entonces todos los componentes son caminos o ciclos

Question

Hay una afirmación en la pág. 109 del libro de teoría de grafos de West

Sea $F$ la diferencia simétrica de dos apareamientos $M, M'$, entonces,

"Supongamos que el grado máximo de un $F$ es menor o igual a 2, entonces todos los componentes son caminos o ciclos"

¿Cómo se podría demostrar esta afirmación? Parece intuitivo que los únicos componentes obtenibles de un grafo con grado $\leq$2 son o bien un camino o un ciclo. ¿Cómo se puede descartar los otros casos?

Answer 1

Sea $G$ un grafo con grado máximo $2$, y tome cualquier camino maximal $x_1, x_2, \dots, x_k$ en $G$. (Por "maximal" quiero decir que no se puede extender desde ninguno de los extremos.)

Luego, los vértices interiores de ese camino $x_2, \dots, x_{k-1}$ ya tienen grado $2$ considerando solo las aristas utilizadas por el camino. Por lo tanto, no tienen más aristas saliendo de ellos. Los extremos $x_1$ y $x_k$ no tienen aristas hacia ningún otro vértice de $G$ (o el camino no sería maximal), por lo que $\{x_1, x_2, \dots, x_k\}$ induce un componente conectado de $G.

Este componente conectado no puede tener aristas $(x_i, x_j)$ con $1 < i < k$ o $j < i < k$, más allá de lo que ya está en el camino, ya que eso aumentaría el grado de $x_i$ o $x_j$ a $3$. Esto descarta todas las posibles aristas menos una: la arista $(x_1, x_k)$. Si está presente, entonces el componente conectado inducido por $\{x_1, x_2, \dots, x_k\}$ es un ciclo; si está ausente, entonces el componente conectado es un camino.