Marginalidad en el teorema del matrimonio de Hall

Question

(a) Que $G=( X \cup Y, E)$ sea un grafo bipartito conectado. Demuestre que cada arista de $G$ se extiende a una coincidencia de $X$ y $Y$ si y sólo si para todo $A \subseteq X$ , $A\neq \emptyset ,X$ tenemos $\left|N_G (A)\right| \gt \left|A\right|$ .

(b) Que $K=( X \cup Y, E)$ sea un grafo bipartito infinito que satisfaga la condición de Hall (es decir $\left|N_G(A)\right| \geq \left|A\right|$ por cada $A \subset X$ ). Demuestre que no contiene necesariamente una correspondencia de $X$ a $Y$ .

Para la parte (a), intenté hacer el $(\Rightarrow)$ parte (no estoy seguro de que sea correcto o no) pero no pude hacer la $(\Leftarrow)$ parte. Sé que debería ser similar a la demostración del teorema del matrimonio de Hall por inducción. Abajo está mi respuesta para $(\Rightarrow)$ .

Como $G$ se extiende a una coincidencia de $X$ a $Y$ entonces todos los vértices deben tener grado $\gt$ 1, por lo que implica que $|N_G (A)| \gt |A|$ para todos $A \subset X$ .

Y en cuanto a la parte b), no tengo ni idea de cómo iniciarla. ¿Podría alguien enseñarme cómo hacerlo, por favor?

Answer 1

$(a, \Longleftarrow)$ Suponga que tiene $|N(A)| > |A|$ para cualquier $A \subseteq X$ tal que $A \neq \varnothing$ y $A \neq X$ . Ahora, elija cualquier borde $e$ y eliminarlo del gráfico, junto con sus puntos finales. Llamemos a este nuevo gráfico $G' = (X' \cup Y', E')$ . Obsérvese que para cualquier $A' \subseteq X'$ tenemos $$|N_{G'}(A')| \geq |N_G(A')| -1 > |A'| - 1,$$ lo que implica $|N_{G'}(A')| \geq |A'|$ . Así, sabemos que existe un $X'$ -saturando la coincidencia en $G'$ y añadiendo la arista $e$ de nuevo, obtenemos que hay un $X$ -saturar la correspondencia utilizando $e$ .

$(a, \Longrightarrow)$ Dejemos que $A$ sea un conjunto mínimo (con respecto a la inclusión) no vacío tal que $|N(A)| = |A|$ demostraremos que, o bien $A = X$ o existe una arista $e$ que no pertenece a ningún $X$ -saturando la coincidencia en $G$ .

Dejemos que $V_1 = A \cup N(A)$ y $V_2 = V \setminus V_2$ . Como el gráfico está conectado, si $V_1 \neq V$ entonces tiene que haber una arista entre $V_1$ y $V_2$ lo llamaremos $e$ . Como toda arista que comienza en $A$ termina, por definición, en $N(A) \subseteq V_1$ Por lo tanto, $e$ tiene que ir de $N(A) = V_1 \cap Y$ a $V_2 \cap X$ . Pero entonces, $e$ no se puede utilizar en un $X$ -de coincidencia saturada, porque utilizaría uno de los vértices de $N(A)$ y ninguno de $A$ , es decir, algún vértice de $A$ se quedaría sin un par.

En cuanto a $(b)$ , utiliza los consejos de @DarijGrinberg.

Espero que esto ayude $\ddot\smile$