Axioma de elección en la teoría de grafos

Question

He elaborado la siguiente prueba para el teorema de que todo grafo conectado tiene un árbol de expansión utilizando el lema de Zorn.

Dejemos que $G$ sea el grafo conexo y considere el conjunto de todos los tress denotado por $S$ . Este conjunto $S$ bajo la relación subgráfica $\subset$ es un conjunto parcialmente ordenado $(S,\subset)$ . Cualquier cadena $C$ del poset es una cadena de tress con respecto a la relación de inclusión. Entonces, la unión de $A=\cup\ T_i$ donde $T_i \in C$ $i \in \{1,2,3,....,n\}$ es el límite superior de la cadena $C$ .

Supongamos que $A$ no es un árbol. Entonces $A$ está desconectado o hay un ciclo presente. Supongamos que $A$ está desconectado, entonces hay dos vértices $x, y \in A$ de tal manera que no hay ningún camino entre ellos. Sea $x \in T_x$ y $y \in T_y$ y $T_x , T_y \in A.$ Desde $T_x$ y $T_y$ es en cadena $C$ (porque $A$ es el límite superior de $C$ ) o bien $T_x \subset T_y$ o $T_y \subset T_x$ y en ambos casos $x$ debe conectarse a $y$ en el árbol más grande. Por lo tanto, $x$ y $y$ está conectado en $A$ que es una contradicción.

Supongamos ahora que existe un ciclo $c \in A$ . Cada borde de $c$ debe aparecer en algún $T_i$ en $C$ Es decir, que $E(c) \subset E(T_i)$ lo cual es una contradicción ya que $T_i$ es acíclico. Por lo tanto, $A$ es un árbol y el límite superior de la cadena $C$ . Entonces, por el lema de Zorn existe un elemento máximo $T^{\ast}$ en $S$ como toda cadena de $S$ tiene un límite superior que es un árbol.

Supongamos que $T^{\ast}$ no es un árbol de expansión, lo que sugiere que hay algún vértice $u \in G$ que no está en $T^{\ast}$ . Sumando las aristas entre algún vértice en $T^{\ast}$ y $x$ crea un nuevo árbol $T^{\ast\ast}$ donde $T^{\ast} \subset T^{\ast\ast}$ que es una contradicción sobre la maximalidad de $T^{\ast}$ .

Apreciaría mucho cualquier comentario sobre los errores o las partes que faltan en la prueba.

Answer 1

Es básicamente correcto. Me he dado cuenta de un fallo de anotación en la prueba que $A$ es acíclico: un ciclo $c$ en $A$ no es un elemento de $A$ por lo que es incorrecto escribir $c\in A$ .

Y podrías decir un poco más en el último párrafo. Si $T^*$ no es un árbol de expansión, hay al menos un vértice $u$ en $G$ que no está en $T^*$ . $G$ está conectado, por lo que hay un camino en $G$ de $u$ a algún vértice $v$ de $T^*$ , digamos que $u=w_0,w_1,\ldots,w_n=v$ . Sea $k\in\{1,\ldots,n\}$ sea mínima, tal que $w_k$ está en $T^*$ Entonces $w_{k-1}$ no está en $T^*$ y es adyacente a $w_k$ que es en $T^*$ , por lo que podemos añadir el vértice $w_{k-1}$ y el borde $\{w_{k-1},w_k\}$ a $T^*$ para obtener un árbol estrictamente mayor, contradiciendo la maximalidad de $T^*$ .