Grado mínimo de un grafo y la existencia de la perfecta coincidencia

Question

Estaba leyendo un resultado donde la siguiente proposición aparece como un paso preliminar (y deja como ejercicio):

Reclamo: Supongamos $G$ es una gráfica en la $n$ vértices ($n$ a y $n \geqslant 3$) con un grado mínimo de al menos $n/2$. Mostrar que $G$ contiene un perfecto maridaje.

Prueba: Por Dirac del teorema, $G$ tiene un ciclo Hamiltoniano $C$. Desde $|C|=n$ es un entero par, el conjunto de "extraño" de los bordes de $C$ da una perfecta combinación para $G$. $\quad\Box$

Siento que el uso del teorema de Dirac para esta afirmación es una exageración. Pero después de probar durante unos días, no podía venir con otras pruebas. Puede usted dar una forma más "directa" prueba de la afirmación de que evita la maquinaria de ciclos Hamiltonianos?

---

Naturalmente, se podría objetar a la vaga requisito de "franqueza". Para aclarar lo que quiero decir con esto, me voy a dar un ejemplo.

Reivindicación 2. Supongamos $G$ tiene un grado mínimo de al menos $n/2$. Mostrar que $G$ está conectado.

Prueba por medio del teorema de Dirac. $G$ tiene un ciclo hamiltoniano como antes, y por lo tanto está conectado. $\Box$

Diferentes pruebas. Vamos a demostrar que cualquier par de vértices $u,v$ están conectados por un camino de longitud en la mayoría de las $2$. Si $uv$ es un borde, hemos terminado. Supongamos que no. A continuación,$N(u) \cup N(v) \subseteq V \smallsetminus \{u,v\}$. Por lo tanto $$ |N(u) \cap N(v)| = |N(u)| + |N(v)| - |N(u) \cup N(v)| \geqslant \frac{n}{2}+\frac{n}{2}-(n-2) = 2 \gt 0. $$ En particular, existe vértice $w$ tal que $uw$ $wv$ son ambos bordes, y hemos terminado. $\quad \Box$

Me parece la prueba por medio del teorema de Dirac mucho menos esclarecedor en este ejemplo. De hecho, como Qioachu señala a continuación, la Reivindicación 2, que podría incluso aparecer como pasos intermedios de Dirac del teorema, haciendo que la anterior prueba cíclica. Mi intención aquí es sólo para señalar que del teorema de Dirac puede ser utilizado como una poderosa caja negra en el asesinato de mucho más fácil de los resultados.

Answer 1

He aquí una alternativa a prueba el uso de la Sala teorema -- no sé si eso cuenta como una más "directa" de la prueba, pero al menos usa un teorema que aborda directamente perfecta elecciones en lugar de un desvío (juego de palabras) a través de los ciclos Hamiltonianos.

Dividir arbitrariamente los vértices en dos conjuntos de $A$ $B$ de igual tamaño. En cada grupo, se encuentra un vértice con un número mínimo de los bordes de la conexión para el otro, y cambiar los dos un mínimo de vértices. Repita esto hasta que el swap ya no aumentará el número total de los bordes de la conexión de los dos conjuntos. (Ya que no hay un número finito de bordes, esto debe suceder en algún momento.) Denotando los dos vértices cuyo intercambio dejarían de aumentar el número de conexiones por $v_A$ $v_B$ y el número de sus bordes dentro de y entre los conjuntos $v_{AA}$, $v_{AB}$, $v_{BA}$ y $v_{BB}$, y contando el número de conexiones entre los grupos antes y después del intercambio, tenemos $v_{AB}+v_{BA}\ge v_{AA}+v_{BB}$. (Podría ser un borde entre el $v_A$$v_B$, pero que actúa en favor de la desigualdad.) De ello se sigue que

$$v_{AB}+v_{BA}\ge \frac12(v_{AB}+v_{BA}+v_{AA}+v_{BB})=\frac12(\deg v_A+\deg v_B)\ge \frac12(n/2+n/2)=n/2\;.$$

Ahora consideremos un subconjunto $X$$A$. Si $|X|\le v_{AB}$, puesto que cada elemento de a $A$ tiene los bordes para que al menos $v_{AB}$ elementos de $B$, $X$ tiene, al menos, como muchos vecinos, $B$ elementos. Si $|X|>v_{AB}$, puesto que cada elemento de a $B$ tiene los bordes para que al menos $v_{BA}$ elementos de $A$$v_{AB}+v_{BA}\ge n/2=|A|$, al menos uno de estos bordes deben llevar a $X$, lo $X$ $n/2$ vecinos,$B$, y por lo tanto, al menos tantos como tiene elementos. Por lo tanto la premisa de que en la Sala del teorema se cumple, y el bipartito gráfico inducida en $A$ $B$ debe contener un perfecto maridaje, que también es un perfecto maridaje en $G$.