Un problema sobre teoría de grafos

En esta publicación voy a resolver el siguiente problema:

Sea $G$ un subgrafo de $K_{20,20}$. Si $G$ tiene un emparejamiento perfecto, probar que $G$ tiene a lo sumo $190$ aristas que no pertenecen a un emparejamiento perfecto.

Demostración:

Supongamos que $G$ es un subgrafo de $K_{20,20}$ y además que $G$ tiene un emparejamiento prefecto. En beneficio de una notación práctica, sean los vértices de $G$ dados por $$\{u_k\}_{k=1}^{20}=\{u_{1},u_{2},...,u_{20}\}$$ y $$\{v_k\}_{k=1}^{20}=\{v_{1},v_{2},...,v_{20}\}$$ etiquedatos de tal forma que $$\{\{u_{k},v_{k}\}\}_{k=1}^{20}=\{\{u_{1},v_{1}\},\{u_{2},v_{2}\},...,\{u_{20},v_{20}\}\}$$ sea un emparejamiento perfecto.

Hagamos $\mathbb{P}$ el conjunto de las parejas $\{k,\ell\}$ de enteros distintos de el conjunto  $[20]:=\{1,\ldots,20\}$, entonces 

$$|\mathbb{P}|=\binom{20}2=\frac{20!}{2!18!}=190$$

Para cada $\{k,\ell\}\in\mathbb{P}$ hagamos

$$E(\{k,\ell\}):=\{u_kv_\ell,u_\ell v_k\}\cap E(G)\;.$$

Es decir: para cada pareja de índices distintos $k$ y $\ell$ ponemos atención a las aristas  $u_ku_\ell$ y $u_\ell v_k$ que atraviesan el emparejamiento $\{u_kv_k,u_\ell v_\ell\}$ de los vértices $u_k$ y $u_\ell$ con los vértices $v_k$, $v_\ell$ y guarde  cualquiera que se encuentre en $G$. Si ninguna está en $G$, entonces $E(\{k,\ell\})=\varnothing$. Si $u_kv_\ell$ es una arista de $G$, pero $u_\ell v_k$ no lo es, entonces $E(\{k,\ell\})=\{u_kv_\ell\}$ y así sucesivamente.

Podemos ver claramemente que si $\{k,\ell\}$ y $\{r,s\}$ son elementos distintos de $\mathbb{P}$, entonces $E(\{k,\ell\})\cap E(\{r,s\})=\varnothing$.

Ahora, supongamos que $G$ tiene una cantidad mayor que $\binom{20}2=190$ aristas que no están en algún emparejamiento perfecto de $G$. Digamos que estas aristas son \textit{defectuosas}. Entonces cada arista $u_kv_k$ con $k\in\{1,\cdots,20\}$ pertenece al emparejamiento perfecto con el que comenzamos, por lo tanto cada una de esas aristas defectuosas tiene la forma $u_kv_\ell$ para algún $k,\ell\in[20]$ con $k\ne\ell$  y por lo tanto pertenece al conjunto $E(\{k,\ell\})$. Existen $190$ de tales conjuntos y una cantidad mayor que $190$ de aristas defectuosas, por lo tanto el \textit{principio de palomar} asegura que algunos $E(\{k,\ell\})$ contienen más de una arista defectuosa. $E(\{k,\ell\})$ contiene a lo sumo las aristas $u_kv_\ell$ y $u_\ell v_k$, entonces si $E(\{k,\ell\})$ contienen al menos dos aristas defectuosas, entonces tiene que darse que $E(\{k,\ell\})$ contenga ambos $u_kv_\ell$ y $u_\ell v_k$, y que ambas de esas aristas sean defectuosas.\\ 

Si ahora consideramos el conjunto de aristas 

$$\beta:=\big\{u_rv_r:r\in[20]\setminus\{k,\ell\}\big\}\cup\{u_kv_\ell,u_\ell v_k\}\;.$$

Este conjunto es obtenido de el emparejamiento perfecto original reemplazando $u_kv_k$ y $u_\ell v_\ell$ con $u_kv_\ell$ y $u_\ell v_k$, manteniendo todas las otras $u_rv_r$ aristas. Se puede concluir que  $\beta$ es un emparejamiento perfecto de $G$, y esto incluye las dos aristas supuestamente defectuosas $u_kv_\ell$ y $u_\ell v_k$ y esto es claramente una contradicción.

La contradicción surgió porque el principio de palomar nos dice que $ E(\{k,\ell\})$ contenía dos aristas defectuosas, y pudimos aplicar el principio de palomar porque asumimos que había más de $190$ aristas defectuosas. Por lo tanto, la contradicción muestra que no puede haber más de $190$ aristas defectuosas. 

De esta manera $G$ tiene a lo sumo $190$ aristas que no pertenecen al emparejamiento perfecto.