¿Es cierto que un grafo conexo tiene un árbol de expansión si el grafo tiene un número incontable de vértices?

Question

He encontrado una prueba de que todo grafo conexo (posiblemente infinito) tiene un árbol de expansión en el Teoría de grafos (cuarta edición) El libro "La vida en el mundo", capítulo 8, utiliza el lema de Zorn, pero en un paso crucial parece suponer secretamente que sólo hay un número contable de vértices.

Así que me pregunto:

¿Es cierto que todo grafo conectado tiene un árbol de expansión? En caso afirmativo, ¿puede demostrarse fácilmente utilizando el lema de Zorn (o el teorema de la ordenación de pozos o el axioma de elección)?

Definiciones, en aras de hacer esta pregunta autónoma: un gráfico es conectado si cada par de vértices está unido por un camino finito, un gráfico es un árbol si está conectada y no tiene ciclos, y un árbol de expansión de $G$ es un árbol $T$ con un conjunto de vértices $V(T)=V(G)$ .

Answer 1

He averiguado la respuesta y alguien me ha pedido que la publique como respuesta, así que respondo a mi propia pregunta por si le sirve a alguien más.

Dejemos que $G$ sea un grafo conexo y considere el conjunto $S$ de todos los árboles $T \subset G$ ordenados por la relación de subgrafos. Queremos aplicar el lema de Zorn, por lo que debemos comprobar primero que toda cadena $\mathcal{C}$ tiene un límite superior, es decir, un árbol que contiene cada $T \in \mathcal{C}$ como un subgrafo. Afirmamos que $T^* = \cup \mathcal{C}$ es precisamente un árbol de este tipo.

Claramente $T$ un subgrafo de $T^*$ por cada $T \in \mathcal{C}$ por la construcción. Lo principal es comprobar que $T^*$ es un árbol. Supongamos que $T^*$ no es un árbol. Entonces $T^*$ está desconectado o tiene un ciclo. Si $T^*$ está desconectado, entonces hay dos vértices $u,v \in T^*$ que no están conectados por un camino en $T^*$ . Pero $u \in T_u$ para algunos $T_u \in \mathcal{C}$ y $v \in T_v$ para algunos $T_v \in \mathcal{C}$ y $\mathcal{C}$ es una cadena, por lo que $T_u \subset T_v$ o $T_v \subset T_u$ y en cualquier caso $u$ está conectado a $v$ por un camino en el árbol más grande, y $T^*$ a su vez contiene este camino, una contradicción. La contradicción a $T^*$ que contiene un ciclo es similar --- cada arista del ciclo debe aparecer en algún lugar de la cadena, y entonces uno de los supuestos árboles de la cadena no es acíclico.

Cada cadena tiene un límite superior, por lo que $S$ tiene un elemento maximal, por el lema de Zorn. Es fácil ver que debe ser un árbol de expansión.