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.


Comentarios

Publicar un comentario

Entradas más populares de este blog

Resolviendo una ecuación diferencial con una solución ingeniosa

  Problema:   Resolver $$ y'=\frac{(x+2y+1)y}{(3x+4y+1)x} $$ Solución:  Reescribiendo la ecuación diferencial ordinaria, tenemos que $$(3x^2+4xy+x)dy-(xy+2y^2+y)dx=0$$ $$\implies(3x^{-1}y^2dy-x^{-2}y^3dx)+(4x^{-2}y^3dy-2x^{-3}y^4dx)+x^{-1}y^2\bigg(\frac{xdy-ydx}{x^2}\bigg)=0$$ $$\implies d\bigg(\frac{y^3}{x}\bigg)+d\bigg(\frac{y^4}{x^2}\bigg)+\frac{y^2}{x}d\bigg(\frac{y}{x}\bigg)=0$$ Haciendo, $\frac{y^3}{x}=u$ and $\frac{y^4}{x^2}=v$ gives $$du+dv+\sqrt{v}d\bigg(\frac{v}{u}\bigg)=0$$ $$\implies\frac{d(u+v)}{\sqrt{u+v}}+\frac{\sqrt{v}}{\sqrt{u+v}}d\bigg(\frac{v}{u}\bigg)=0$$ $$\implies\frac{d(u+v)}{\sqrt{u+v}}+\dfrac{\sqrt{\frac{v}{u}}}{\sqrt{1+\frac{v}{u}}}d\bigg(\frac{v}{u}\bigg)=0$$ Integrando, tenemos que $$2\sqrt{u+v}+\frac{\sqrt{v(u+v)}}{u}-\ln\bigg(\frac{\sqrt{v}+\sqrt{u+v}}{\sqrt{u}}\bigg)=C$$ $$\implies\boxed{\bigg(2+\frac{1}{y}\bigg)\sqrt{\frac{y^4}{x^2}+\frac{y^3}{x}}-\ln\bigg(\frac{y^2}{x}+\sqrt{\frac{y^4}{x^2}+\frac{y^3}{x}}\bigg)+\frac{1}{2}\ln\bigg(\fr...
Leer más

Teorema de Hall (Teoría de grafos)

En esta primera publigación voy a demostrar el teorema de Hall (un principio muy famoso en teoría de grafos), haciendo uso del   teorema de König-Egerváry. Recordemos que el teorema de König-Egerváry, nos dice que: "Sea $G$ un grafo bipartito. El máximo número de aristas en un emparejamiento en $G$ es igual al mínimo número de vértices en una cubierta de aristas para $G$". mientras que el teorema de Hall nos dice que:  "Sea $G$ un grafo bipartito con conjuntos partitos $X$ y $Y$. Entonces $X$ puede ser emparejado en $Y$ si, y sólo si, $\forall S\subseteq X: |N(S)|\geq |S|$". En otras palabras el teorema de Hall nos dice que cada subconjunto $S$ de $X$ tiene suficientes vértices adyacentes en $Y$. Demostración del teorema de Hall: Veamos que $(\implies)$  Si $G$ tiene un emparejamiento de tamaño $|X|$, es decir si $X$ puede ser emparejado en $Y$, entonces para todo subconjunto $S$ de $X$ se tiene que $|S|\leq |N(S)|$. $(\Longleftarrow)$ Queremos probar que si $\foral...
Leer más

Un resultado de teoría de grafos

En esta publicación voy a demostrar el siguiente resultado de teoría de grafos: Si $G$ es un grafo bipartito regular de grado $k$, entonces $G$ contiene un emparejamiento perfecto. Demostración: Supongamos que $G$ es un grafo bipartito regular de grado $k$ (es decir, $G$ es un grafo $k-$bipartito regular), con conjuntos bipartitos $X$ y $Y$.   Sea $A \subseteq X$ y sea $t$  el número de aristas con un extremo en $X$. Como cada vértice en $X$ tiene grado $k$, entonces que $k|A|=t$. De manera análoga, cada vértice en $N(A)$ tiene grado $k$, entonces $t$ es menor o igual que $k|N(A)|$, esto es, $t\leq k|N(A)|$. Por lo tanto $|A|$ es lo sumo $|N(A)|$. Por lo tanto, por el teorema de Hall, existe un matching covering  $X$, o de manera equivalente, cada máximo matching cubre $X$.  Así, por un argumento similar, se puede encontrar que cada máximo matching cubre $Y$ y por lo tanto $G$ tiene un emparejamiento perfecto.
Leer más