Como soy muy detallista, propongo la siguiente solución.
Sea $G = (V,E) = (A\cup B,E)$ sea un grafo bipartito equilibrado (simple) con $|V| = 2 \cdot n$ para $n \in \mathbb N$ . Si $|E| > k \cdot n$ para $0 \leq k < n$ entonces $G$ contiene una coincidencia de tamaño $k+1$ .
Suponemos que $n>1$ (de lo contrario la afirmación es evidente) y utilizar la inducción sobre $k$ (para gráficos del tipo descrito).
Denote $E(U,W) := \{u w \in E:: u \in U\setminus W \wedge w \in W\setminus U\}$ para $U,W \subseteq V$ como el conjunto de aristas entre conjuntos de vértices $U$ y $W$ en $G$ . Utilizamos $d(v)$ para $v \in V$ para denotar el número de aristas en $G$ incidente con $v$ . Por fin, $N(v) = \{w \in V:: v w \in E\}$ son los vecinos de $v$ en $G$ .
Caso 0 ( $k = 0$ ): Desde $G$ contiene al menos una arista, se deduce que contiene una coincidencia de tamaño $1 = 0 + 1$ .
Caso 1 ( $k = 1$ ): Entonces, $G$ contiene al menos $3$ bordes. Supongamos que todas las aristas son adyacentes. Elija cualquier arista $xy \in E$ . Si hay aristas distintas $e_1,e_2 \in E\setminus \{xy\}$ incidente con $x$ y $y$ respectivamente, son disjuntos porque $G$ es bipartita, es decir, no contiene ciclos Impares (si $e_1$ y $e_2$ eran adyacentes a través de otro vértice $z \in V\setminus \{x,y\}$ entonces $x y z x$ es un triángulo). Esto es una contradicción con la suposición. Entonces, $G$ contiene al menos $2$ aristas disjuntas, es decir, un emparejamiento de tamaño $2 = 1 + 1$ .
Caso 2 ( $k > 1$ ): Sabemos que $G$ contiene un $M \subseteq E$ de tamaño $k = (k-1)+1$ por hipótesis de inducción porque $|E|>k\cdot n > (k-1)\cdot n$ .
Sea $A' \subseteq A$ y $B' \subseteq B$ sea el conjunto de (por $M$ ) vértices coincidentes en $G$ . Vemos $|A'| = k = |B'|$ . Desde $k<n$ hay $n-k$ vértices no coincidentes que quedan en $A'' := A\setminus A'$ y $B'' := B\setminus B'$ es decir, $|A''| = n-k = |B''|$ .
Si hay una arista $a'' b'' \in E$ con $a'' \in A''$ y $b'' \in B''$ entonces podemos aumentar la concordancia $M$ a $M \cup \{a'' b''\}$ de tamaño $k+1$ . Por lo tanto, supongamos que $E(A'',B'') = \emptyset$ .
Sea $a b \in M$ sea una arista con $a \in A'$ y $b \in B'$ . Si podemos encontrar vértices $a' \in A''$ y $b' \in B''$ con $a b', a' b \in E$ , entonces podemos cambiar la concordancia $M$ a un $(M\setminus \{ab\}) \cup \{a b', a' b\}$ de tamaño $k+1$ . Por lo tanto, supongamos que esto es imposible, es decir, $\forall ab \in M: (N(a) \subseteq B' \vee N(b) \subseteq A') \wedge d(a) + d(b) \leq n + k < 2 \cdot n$ .
Caso 2.1 ( $\forall a b \in M: d(a) + d(b) = n + k$ ): Entonces, $\{d(a), d(b)\} = \{n,k\}$ . En consecuencia $G[A' \cup B'] = K_{k,k}$ es decir, los vértices de $A'$ y $B'$ forman un subgrafo bipartito completo en $G$ . Por lo tanto, si hay un vértice $a_0 \in A'$ con $d(a_0) = n$ entonces $\forall a \in A': d(a) = n$ y $\forall b \in B': d(b) = k$ . Por simetría del argumento, esto es válido análogamente para cualquier $b_0 \in B'$ con $d(b_0) = n$ . Sin pérdida de generalidad, supondremos un vértice $a_0 \in A'$ con $d(a_0) = n$ .
Además, desde $E(A'',B'') = \emptyset$ y $\forall a \in A': d(a) = n$ sigue $\forall b \in B: d(b) = k$ y así $k \cdot n < |E| = \sum_{b \in B} d(b) = n \cdot k$ lo cual es una contradicción.
Caso 2.2 ( $\exists a_1 b_1 \in M: d(a_1) + d(b_1) \leq n + k - 1$ ): Definir $H := G - \{a_1, b_1\} = (V',E')$ con $|V'|=2 \cdot (n-1)$ . Entonces, $|E|-(n+k-1) \leq |E'|$ y así $(k-1)\cdot (n-1) = k \cdot (n-1+1)-(n-1+k) = k \cdot n - (n+k-1) < |E'|$ .
De ello se deduce que $H$ tiene un $M' \subseteq E(H)\subsetneq E(G)$ de tamaño $k$ por hipótesis de inducción. Aumentamos $M'$ a $M' \cup \{a_1 b_1\}$ como coincidencia de $G$ de tamaño $k+1$ .
