G es un grafo bipartito, donde para cada arista e=(a,b)[a,b están en A,B] d(a)>d(b), y d(a)>0, demuestre que existe un emparejamiento que satura A

Question

Creo que la dirección es definitivamente HALL, intenté usar la inducción sobre el tamaño de S, donde S es algún subgrupo de A, pero no fui capaz de completar el proceso.

Answer 1

Una forma de hacerlo es la siguiente:

Primero hay que demostrar un lema: Si $G$ es un grafo bipartito con bipartición $X,Y$ y ningún vértice aislado en $X$ , de manera que $d(x)\geq d(y)$ siempre que $x\in X$ y $y\in Y$ son adyacentes. Entonces $|X|\leq|Y|$ .

Entonces, para cada subconjunto $S$ de $A$ se encuentra que las condiciones de grado siguen siendo válidas para el subgrafo inducido por $S\cup N(S)$ . Ahora el lema implica que $|S|\leq|N(S)|$ y has verificado la condición de Hall.

Se puede demostrar el lema por inducción en el grado máximo. Aquí hay algunas pistas para la demostración del lema.

Dejemos que $k$ sea el grado máximo. La base de inducción ( $k=1$ ) es simple. Para el paso de inducción, dejemos que $G$ sea un contraejemplo más pequeño para la afirmación con grado máximo $k>1$ . Sea $P$ sean los vértices de $X$ con grado $k$ y $Q$ los vértices en $Y$ con grado $k$ .

Ahora demuestre las siguientes afirmaciones:

1. $P$ no puede estar vacío.

2. $Q$ no puede estar vacío.

3. Todos los bordes que comienzan en $Q$ debe ir a $P$ .

4. Hay una coincidencia de $Q$ en el subgrafo inducido por $P\cup Q$ .

5. Si se eliminan las aristas de este emparejamiento se obtiene un contraejemplo más pequeño para la afirmación. Esta contradicción final muestra que no puede existir tal contraejemplo.

Prueba del punto 2 (suponiendo que ya hemos demostrado que $P$ no está vacío): Supongamos que $Q$ está vacía. Ahora eliminamos una sola arista $px$ que tiene un punto final $p$ en $P$ . El gráfico restante sigue cumpliendo las condiciones de grado (el grado de los vértices en $Q$ sólo puede ser menor, el grado de los vértices en $P$ no se modifican, excepto el grado de $p$ que ahora es $k-1$ y porque $Q$ estaba vacía todos los vecinos de $p$ tienen un grado como máximo $k-1$ ). Pero $X$ y $Y$ siguen siendo los mismos, así que $G$ no era el menor contraejemplo. Contradicción.