Dejemos que $n\leq m$ sean enteros positivos.
¿Cuál es el valor máximo posible de $d$ tal que existe un grafo bipartito $X,Y$ con $|X|=n$ , $|Y|=m$ y el grado mínimo $d$ que no admite $X$ ¿Saturación de coincidencias?
Respuesta
¿Demasiados anuncios?
Es $d = \lfloor\frac{n-1}{2}\rfloor$ .
Cuando $d < \frac n2$ tenemos la siguiente construcción. Partición $X$ en $X_1$ y $X_2$ con $|X_i| = d+1$ y la partición $Y$ en $Y_1$ y $Y_2$ con $|Y_1| = d$ . A continuación, añada todas las aristas entre $X_i$ y $Y_i$ para $i=1,2$ . Esto no tiene $X$ -saturando la concordancia porque el $d+1$ vértices en $X_1$ todos quieren ser emparejados con el mismo $d$ vértices en $Y_1$ .
Cuando $d \ge \frac n2$ Esto no funciona. (Los vértices en $Y_2$ no tendrá el grado mínimo correcto). En este caso, podemos demostrar que hay un $X$ -saturar la coincidencia verificando la condición de Hall. Sea $S \subseteq X, S \neq \varnothing$ . Entonces:
- Si $|S| \le \frac n2$ entonces $|N(S)| \ge d \ge |S|$ porque sólo un vértice de $S$ ya tiene $d$ vecinos.
- Si $|S| > \frac n2$ entonces $N(S) = Y$ porque $|X \setminus S| < \frac n2 \le d$ por lo que cada vértice de $Y$ necesita un vecino en $S$ para alcanzar el grado mínimo de $d$ . $|N(S)| = |Y| \ge |X| \ge |S|$ .
