Subgrafo bipartito de grado mínimo

Question

Demostrar que todo gráfico $G$ con un grado mínimo $2m$ tendrá un subgrafo bipartito de grado mínimo $m$ .

He intentado esta prueba tomando primero un vértice $v$ y considerarlo en conjunto $D_0$ . Entonces estoy tomando m de sus vecinos (de $2m$ ) para formar un conjunto $D_1$ . Mi intención principal es dividir todos los vértices de G en $D_i$ y crear dos particiones con $i$ s como incluso en una partición y $i$ s como impar en otra partición.

Pero tengo una dificultad para demostrar que no existe ninguna arista entre dos $D_i$ en diferentes niveles

Answer 1

Una pista:

• Dejemos que $G_0$ sea cualquier subgrafo bipartito máximo de $G$ .
• Dejemos que $v_i \in V$ sea algún vértice del menor grado en $G_i$ .
• Si $\mathrm{deg}_{G_i}(v_i) \geq m$ entonces ha terminado (y la secuencia se detiene), de lo contrario establezca $G_{i+1}$ para ser el gráfico con $v_i$ desplazado al otro lado (y se han añadido o eliminado los bordes adecuados para que $G_{i+1}$ es también un subgrafo bipartito máximo de $G$ ).
• Obsérvese que con cada vuelta, el número de aristas de $\{G_i\}_i$ estrictamente aumenta, pero la única manera de que la secuencia se detenga es cuando $\mathrm{deg}_{G_\text{end}}(u) \geq m$ para todos $u \in V$ .

Espero que esto ayude $\ddot\smile$