La coincidencia máxima contiene una arista que contiene una hoja de un árbol.

Question

Quería demostrar lo siguiente utilizando el lema de Berges ( https://en.wikipedia.org/wiki/Berge%27s_lemma ): Sea $T=(V,E)$ sea un árbol con $n:=|V| \geq 3$ . Entonces cualquier máxima coincidencia $M_{max}$ contiene al menos una arista $E$ que contiene una de las hojas de $T$ .

Desde $T$ es un árbol que tiene al menos dos hojas $l_1,l_2$ y como $n \geq 3$ hay un camino $P$ conectando $l_1$ a $l_2$ tal que $|P| \geq 3$ . Si $M$ no contendría ninguna arista $E$ con $l_1 \in E$ o $l_2 \in E$ entonces $P$ sería casi un camino aumentado, en contradicción con el lema de Berge. Todo lo que necesito es que $P$ es alternativo, pero no sé si es posible construir $P$ de esta manera.

Edición: Después de buscar he encontrado que algo similar se ha utilizado en la demostración del teorema del árbol por Adam Lowrance en $\alpha^{'}(G)\geq\frac{n}{1+\Delta(G)}$ . Sin embargo, parece que utiliza una definición de camino aumentado diferente a la que se utiliza en la wikipedia del Lemma de Berges.

Answer 1

La forma directa de demostrar esta afirmación es simplemente ver lo que sucede cuando buscamos un camino de aumento, comenzando en cualquier vértice no emparejado. (El vértice inicial puede ser o no una hoja; no importa. Sin embargo, podemos suponer que existe algún vértice no coincidente desde el que empezar: si no es así, $M_\max$ sería una combinación perfecta y cubriría todas las hojas).

Sólo alternaremos los dos pasos siguientes:

1. Desde la posición actual, camina a lo largo de un borde que no sea parte de $M_\max$ .
2. Desde la posición actual, camina a lo largo de un borde que es parte de $M_\max$ .

Repetiremos estos dos pasos hasta que el paso que intentamos hacer sea imposible. Obsérvese que cuando empezamos en un vértice no coincidente, el primer paso debería ser siempre posible: cuando $n \ge 2$ cada vértice tiene al menos una arista, y si no coincide, esa arista no forma parte de $M_\max$ .

¿Cómo podemos atascarnos? Hay dos opciones:

1. Nos quedamos atascados en el paso 1: fuimos al vértice actual a lo largo de una arista que forma parte de $M_\max$ pero ahora no hay bordes fuera de él que no formen parte de $M_\max$ . Entonces nuestro vértice actual debe ser una hoja cubierta por el emparejamiento, y tenemos lo que queríamos.
2. Nos quedamos atascados en el paso 2: fuimos al vértice actual a lo largo de una arista que no forma parte de $M_\max$ pero ahora no hay bordes fuera de él que son parte de $M_\max$ . Entonces el vértice actual tampoco está emparejado, y el camino que recorrimos es un $M_\max$ -que es una contradicción con el lema de Berge.

Y lo que es más importante, como el grafo es un árbol, tenemos que atascarnos: no hay ciclos, así que no podemos seguir caminando eternamente.