Problems-Solving Strategy

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 índi...

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.

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...