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.



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