Máxima coincidencia de un gráfico frente a su grado mínimo

Question

¡Estoy tratando de hacer el siguiente problema, parece fácil pero no puedo hacerlo!

---

Sea G un grafo simple con $n\geq 2\delta$ . Demostrar que $\alpha' \geq \delta$

donde

$\delta=$ grado mínimo en $G$

$\alpha'=$ el número de aristas en una coincidencia máxima de $G$

y $n$ el número de vértices de G.

---

Pensé esto: si $M$ es una coincidencia máxima de $G$ y supongamos $|M| < \delta$ Entonces, demuestre de alguna manera que cualesquiera dos vértices no cubiertos por M están conectados por un camino que aumenta M y derive una contradicción, pero, incluso esto, no puedo ver cómo hacerlo.

Se agradece cualquier ayuda. Gracias.

Answer 1

Dejemos que $G$ sea un grafo simple (no necesariamente finito-véase el post script) con grado mínimo $\delta$ y el orden $|V(G)|\ge2\delta.$ Dejemos que $M$ sea una coincidencia máxima en $G,$ y asumir para una contradicción que $|M|=m\lt\delta.$

Entonces $W=V(G)\setminus V(M)$ es independiente y $|W|\ge2.$ Elige dos vértices distintos $x,y\in W.$ Hay al menos $2\delta$ bordes entre $V(M)$ y $\{x,y\}.$ Desde $2m\lt2\delta,$ podemos elegir una arista $uv\in M$ tal que haya al menos tres aristas entre $\{u,v\}$ y $\{x,y\}.$ Sin pérdida de generalidad, podemos suponer que dos de esas aristas son $ux$ y $vy.$ Entonces $M-uv+ux+vy$ es una coincidencia en $G$ de tamaño $m+1,$ contradiciendo nuestra suposición de que $M$ es una coincidencia máxima.

P.D. ¿Y si $G$ es un gráfico infinito? Si $\delta$ es un cardinal infinito, entonces cualquier correspondencia máxima tiene una cardinalidad de al menos $\delta.$ (Se asume el axioma de elección.) Si $\delta$ es finito, y si no hay ninguna coincidencia de tamaño $\delta,$ entonces hay una coincidencia máxima, y el argumento anterior está bien.