Una prueba por contradicción

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.