Versión deficitaria del teorema de Hall - ¡Ayuda!

Question

Así que tengo las siguientes dos preguntas de examen:

Sea $G$ sea un grafo bipartito con clases de vértices $A$ y $B$ donde $|A|=|B|=n$ . Supongamos que $G$ tiene una titulación mínima de $\frac{n}{2}$ . Utilizando o no el teorema de Hall, demuestre que $G$ tiene una correspondencia perfecta. Determinado (con justificación) una cubierta de vértices de tamaño mínimo.

Sea G un grafo bipartito con clases de vértices A y B, donde $|A|=|B|=n$ . Supongamos que $k \in N$ y que $G$ tiene una titulación mínima de $\frac{n-k}{2}$ . Demuestre que G tiene un emparejamiento de tamaño al menos $n-k$ .

Creo que la primera pregunta equivale a demostrar que cualquier grafo bipartito k-regular satisface la condición de Hall y, por tanto, contiene un emparejamiento perfecto, pero no consigo averiguar por qué se dan los grados. La segunda parte parece que debería utilizar la versión deficiente del teorema de Hall; si $N_G(S) \geq |S| - d $ el $ G $ contiene una coincidencia de tamaño $n-k$ . Sin embargo, no veo cómo encontrar $N_G(S) \geq |S| - d$ .

Answer 1

Empezamos por la primera pregunta. Para demostrar que $G$ tiene una correspondencia perfecta demostramos que $G$ cumple las condiciones del teorema de Hall. En efecto, sea $A’$ sea un subconjunto arbitrario no vacío de $A$ . Si $|A’|\le n/2$ entonces elige cualquier vértice $v\in A’$ y señalar que $|A'|\le n/2\le |N(v)|\le |N(A’)|$ . Si $|A’|> n/2$ entonces $A’$ se cruza con $N(u)$ para cada vértice $u\in B$ porque ambos $A’$ y $N(u)$ son subconjuntos de $A$ , $|A|=n$ y $|A’|+|N(u)|>n/2+n/2=n$ . Así $u\in N(A’)$ . Por lo tanto $N(A’)=B$ y $|A’|\le |A|=n=|B|=|N(A’)|$ .

Desde $G$ es bipartito, cada uno de los conjuntos $A$ y $B$ constituye su cubierta de vértices de tamaño $n$ . Este valor no puede disminuir, porque $G$ tiene un mathching perfecto de tamaño $n$ por lo que cada subconjunto formado por menos de $n$ vértices de $G$ se perdería un borde del emparejamiento.

Podemos reducir la segunda pregunta a la primera de la siguiente manera. Añadir a cada una de las clases $A$ y $B$ de $G$ $k$ nuevos vértices adyacentes a todos los vértices de la otra clase. De este modo creamos un grafo bipartito $G^*$ con las clases de vértices $A^*$ y $B^*$ de tamaño $n+k$ cada uno con una titulación mínima $\frac {n-k}2+k=\frac {n+k}2$ . Por lo tanto $G^*$ tiene un mathching perfecto $M^*$ que tiene un tamaño $n+k$ . Como máximo $2k$ bordes de $M$ inciden en nuevos vértices. Cuando eliminamos estas aristas de $M^*$ obtenemos una coincidencia $M$ para $G$ de tamaño mínimo $n+k-2k=n-k$ .

Answer 2

Por contradicción, supongamos $G$ no tiene una correspondencia perfecta. Dado que el grado mínimo de cada vértice es $n/2$ cualquier $S\subseteq A$ con $\lvert S\rvert\le n/2$ debe tener $\lvert N(S)\rvert\ge n/2\ge\lvert S\rvert$ . Así que debe haber al menos una $S\subseteq A$ con $\lvert N(S)\rvert<\lvert S\rvert$ y $\lvert S\rvert>n/2$ . Entonces observe que $B\setminus N(S)$ será una colección de vértices cuya vecindad tenga menos de $n/2$ vértices, lo que implica que el grado medio de cada uno de estos vértices es inferior a $n/2$ una contradicción.

Creo que la segunda parte puede demostrarse de forma similar.