En teoría de grafos una técnica bastante usada es proceder suponiendo que la proposición es falsa y analizando las consecuencias de dicha suposición hasta llegar a una contradicción.
El siguiente teorema fue realizado por Erdös en 1965.
Teorema. (Erdös) Cada grafo sin lazos contiene un subgrafo bipartito generador F tal que d_F(v)\geq \frac{1}{2} d_G(v) para todo v\in V
Demostración.
Sea G un grafo sin lazos. G tiene un subgrafo generador bipartito, uno de ellos es, por ejemplo, el subgrafo generador vacío. Sea F=F[X, Y] un subgrafo generador bipartito con el máximo número de enlaces. Afirmamos que F satisface la propiedad requerida. Supongamos que no, entonces existe algún vértice tal que
d_F(v) < \frac{1}{2} d_G(v)
Sin pérdida de generalidad, podemos suponer que v está en el conjunto X. Consideremos el subgrafo bipartito generador F’ cuyo conjunto de enlaces consiste de todos los enlaces de G con un terminal en X\setminus v y otro en Y\setminus v . El conjunto de enlaces de F’ es el mismo conjunto de enlaces de F excepto por aquellos enlaces incidentes en v, aquellos que están en F no están en F’ y aquellos que no están en F están en F’.
\begin{aligned}e(F')=e(F)-d_F(v)+(d_G(v)-d_F(v))\\=e(F)+(d_G(v)-2d_F(v))>e(F) \end{aligned}Pero esto contradice que F sea el subgrafo bipartito generador con mayor número de enlaces.