Dejemos que $G=\left\langle V,E\right\rangle$ sea un grafo no dirigido con $V=\left\{ S\subset\left\{ 1,2,\ldots,9\right\} \mid\left|S\right|\in\left\{ 3,4\right\} \right\}$ y $E\left\{ \left(u,v\right)\mid u\subset v \lor v\subset u\right\}$ . Me gustaría demostrar que este grafo tiene un ciclo euleriano, por lo que además de mostrar que el grado de todos los vértices es par (bastante fácil) también quiero demostrar que está conectado, pero todos los intentos hasta ahora han acabado muy desordenados, con división en casos por existencia de un camino entre dos vértices cualesquiera. ¿Hay una manera más elegante?
Respuestas
¿Demasiados anuncios?
mrseaman
Puntos
161
Sugerencia: piense en un camino desde $S_1 \in V$ a $S_2 \in V$ como una secuencia de operaciones $S \mapsto S'$ donde $S'$ se obtiene de $S$ ya sea añadiendo un nuevo elemento si $|S| = 3$ o eliminar un elemento si $|S| = 4$ . Ahora diseñe una estrategia que transforme cualquier $S_1$ en cualquier $S_2$
Parece que la forma más fácil de hacerlo sería a través de la inducción. Dejemos que $G_n$ sea el gráfico en el $3$ - y $4$ -subconjuntos de elementos de $\{1,\ldots, n\}$ con la misma regla para las aristas. Es fácil ver que $G_4$ está conectado (¿por qué?). Dado que $G_{n-1}$ está conectado, para demostrar que $G_n$ está conectada, bastaría con tomar un vértice arbitrario en $v \in V(G_n) \setminus V(G_{n-1})$ y mostrar que tiene un camino hacia algunos vértice en $G_{n-1}$ . Conectividad de $G_{n-1}$ sería entonces suficiente para llegar desde $v$ a cualquier vértice que desee, incluyendo los otros vértices de $V(G_n) \setminus V(G_{n-1})$ aunque probablemente merezca la pena desarrollar ese argumento con más detalle por ti mismo.
