Emparejamiento perfecto en un grafo bipartito con una secuencia de grados restringida

Question

Dado un grafo bipartito G con dos conjuntos de partición $U$ y $V$ del mismo tamaño $n$ . En cada conjunto, hay d vértices de grado (n-d+1), y n-d vértices de grado (n-d). ¿Podemos encontrar una correspondencia perfecta en este grafo?

Así que, básicamente, los dos conjuntos son iguales en cuanto a la secuencia de grados, aunque no se sabe cómo son los vértices adyacentes entre sí. He intentado utilizar el teorema de Hall, pero me he quedado atascado. Tomemos cualquier subconjunto S de U que contenga algunos vértices de grado n-d+1 y otros de grado n-d, entonces no soy capaz de demostrar $|N(S)| \geq |S|$ .

EDIT: La primera pregunta está resuelta y ahora una pregunta más general y quizás orientada a la investigación es: ¿Y si en cada conjunto $U$ y $V$ Hay $d$ vértices de grado AL MENOS $(n-d+1)$ y $n-d$ vértices de grado AL MENOS $(n-d)$ . ¿Todavía podemos encontrar una combinación perfecta?

Aquí falla el método de la pregunta anterior.

Answer 1

Puedes atar $\lvert N(S)\rvert$ desde abajo considerando el peor caso de que todos los vecinos tengan el grado máximo, $n-d+1$ . Entonces cada vértice en $S$ de grado $n-d+1$ tiene tantas aristas de salida como aristas de entrada tiene un vecino en el peor de los casos, por lo que el "balance de costes" de dicho vértice es neutral. Cada vértice de $S$ de grado $n-d$ "guarda" un borde, pero puede haber como máximo $n-d$ de estos en $S$ , por lo que sólo $n-d$ se pueden "guardar" los bordes, mientras que $n-d+1$ habría que "salvar" bordes para "salvar" a un vecino en el peor de los casos. Por lo tanto, no se puede "salvar" a ningún vecino ni siquiera en el peor de los casos, por lo que debe haber tantos vecinos como vértices en $S$ .

Puedo escribirlo en fórmulas si quieres, pero dijiste que querías una pista.

[Editado en respuesta a la solicitud de fórmulas:]

Dado que todas las aristas que inciden en un vértice de $S$ también inciden en un vértice de $N(S)$ tenemos

$$\sum_{w\in N(S)}\deg(w)\ge\sum_{v\in S}\deg(v)\;.$$

Si $S$ contiene $n_-$ vértices de grado $n-d$ y $n_+$ vértices de grado $n-d+1$ entonces

$$\begin{eqnarray} \sum_{v\in S}\deg(v)&=&n_-(n-d)+n_+(n-d+1)\\\ &=&(n_-+n_+)(n-d+1)-n_-\\\ &=&\lvert S \rvert (n-d+1)-n_-\\\ &\ge&\lvert S \rvert (n-d+1)-(n-d)\;, \end{eqnarray}$$

ya que sólo hay $n-d$ vértices de grado $n-d$ . Por otra parte, como ningún vértice tiene un grado superior a $n-d+1$ también tenemos

$$\sum_{w\in N(S)}\deg(w)\le \lvert N(S) \rvert (n-d+1)\;.$$

La combinación de todo esto da como resultado

$$\lvert N(S) \rvert (n-d+1) \ge \lvert S \rvert (n-d+1)-(n-d)\;,$$ $$\lvert N(S) \rvert \ge \lvert S \rvert -\frac{n-d}{n-d+1}\;.$$

Pero $\lvert N(S) \rvert$ y $\lvert S \rvert$ son enteros y el último término es menor que $1$ por lo que podemos eliminar el último término para concluir que $\lvert N(S) \rvert\ge\lvert S \rvert$ . Enlazando esto con la respuesta original, cada vértice en $S$ de grado $n-d$ puede cambiar el balance en la penúltima desigualdad como máximo $1$ y hay como máximo $n-d$ tales vértices, por lo que el equilibrio sólo puede ser cambiado por $n-d$ pero tendría que cambiar por $n-d+1$ para hacer una diferencia en la última desigualdad, donde la división por $n-d+1$ corresponde al hecho de que tenemos que "salvar" $n-d+1$ aristas para "salvar" a un vecino en el peor de los casos.