Emparejamiento y teoría de grafos

Question

Demostrar que si $G=(A \cup B,E)$ es bipartita y $|A|=n$ y $|B|=n$ , $|E|>kn$ entonces $G$ contiene una coincidencia de tamaño $k+1$

No pido una solución sino una idea de cómo enfocar el problema. Otra pregunta no relacionada es : Estoy teniendo problemas con la teoría de grafos, me sé todos los teoremas y lemas, pero cuando se trata de preguntas de los exámenes me siento inútil, ¿tiene algún consejo para mí sobre cómo mejorar en la solución de preguntas de la teoría de grafos? ¿O un truco útil sobre cómo abordar las preguntas de la teoría de grafos?

Answer 1

Encontré una solución si tenía $n$ vértices : Usando la inducción sobre k, y el hecho de que tiene que haber un vértice de grado al menos 2k+1 podemos encontrar un vértice que no estaba en el emparejamiento anterior , y añadir la arista que conecta ambos al emparejamiento (también necesitamos usar el hecho de que eliminar cualquier vértice sigue preservando la propiedad de tener más de $(k-1)$ (n-1) aristas)

Answer 2

No tengo una solución, sino una pregunta: Si elijo una estrella para $G$ con $6$ vértices (es decir, uno como centro de la estrella y $5$ vértices satélites), entonces $G$ es bipartito con $|V(G)| = 2 \cdot 3$ y $|E(G)| = 5 > 1 \cdot 3 = 3$ . Pero cada estrella contiene una coincidencia de a lo sumo una arista y no $k+1 = 2$ en este caso. ¿Crees que tienes el teorema correcto?

Answer 3

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

Answer 4

En nuestro caso la simple inducción sobre $n$ y $k$ funcionaría, sólo tiene que observar que si hay una correspondencia de tamaño $k$ entonces debemos tener dos vértices que son matced y la suma de su grado no es más que $n+k-1$