En todo grafo bipartito G, existe un vértice v tal que v está emparejado en todo emparejamiento máximo SIN Gallai?

Question

Un vértice esencial es un vértice que está incluido en todos los emparejamientos máximos de un grafo. Y en cualquier grafo bipartito conexo existe tal vértice. La prueba está dada en esta respuesta . Pero esta demostración es a través del teorema de Gallai. ¿Hay alguna otra forma de demostrar lo mismo? ¿Por ejemplo, utilizando el teorema de Konig o el teorema de Hall?

Se agradecería cualquier ayuda.

Answer 1

Dejemos que $G$ sea un grafo bipartito conexo con bipartición $\{A,B\}$ . (Suponemos que $G$ tiene más de un vértice, y por lo tanto $A$ y $B$ son no vacíos, de lo contrario la afirmación es falsa). Si $G$ contiene una coincidencia de $A$ entonces cada vértice de $A$ es esencial. De lo contrario, por el teorema de Hall, existe $S\subseteq A$ tal que $|N(S)|<|S|$ . Elija una de las más pequeñas como $S$ . Afirmamos que cada vértice de $N(S)$ es esencial, completando así la prueba porque $G$ conectado con más de $1$ vértice y $|S|>0\implies|N(S)|>0$ .

Dejemos que $v\in N(S)$ y supongamos que un $M$ en $G$ no contiene $v$ . Encontramos un camino de aumento que comienza en $v$ , demostrando que $M$ no es máxima. Sea $H$ sea el subgrafo de $G$ inducido por $S\cup N(S)$ . Sea $X$ sea el conjunto de vértices de $N(S)$ que se puede alcanzar desde $v$ por un camino alternativo contenido en $H$ y $Y$ el conjunto de vértices penúltimos de estos caminos. Si $Y=\varnothing$ entonces $v$ tiene un vecino no coincidente en $X$ por lo que su arista compartida es un camino de aumento.

Supongamos, en cambio, que $Y\neq\varnothing$ . $M$ proporciona una biyección de $X\setminus\{v\}$ y $Y$ Así que $|Y|=|X|-1\le N(S)-1<|S|-1\implies Y\subsetneq S$ . Entonces hay vértices adyacentes $x\in X$ y $u\in S\setminus Y$ -de lo contrario, $$N(S\setminus Y)\subseteq N(S)\setminus X\implies|N(S\setminus Y)|\le|N(S)|-|X|<|S|-|Y|=|S\setminus Y|\,,$$ así que $S\setminus Y$ contradiría la minimidad de $S$ .

Dejemos que $P$ sea un camino alternativo desde $v$ a $x$ . $u$ no es compatible, de lo contrario, podríamos ampliar $P$ por el filo inigualable $xu$ y la arista coincidente de $u$ creando un camino alternativo a partir de $v$ con el penúltimo vértice $u$ pero $u\notin Y$ . Porque $u$ no coincide, podemos ampliar $P$ por el filo inigualable $xu$ para crear un camino de aumento, completando la prueba.