¿Los subgráficos de #% regular $k$% #% tienen una correspondencia perfecta: una prueba sin pasillo ' s Teorema de matrimonio?

Question

Hay varias maneras de describir a este resultado:

Teorema: Para $k \in \{1,2,\ldots,n\}$ cualquier $k$-regular subgrafo de $K_{n,n}$ tiene un perfecto maridaje (también conocido como un $1$-factor).

Tiendo a pensar que es:

Teorema: Para, $k \in \{0,1,\ldots,n-1\}$ cualquier $k \times n$ latina rectángulo se extiende a una $(k+1) \times n$ latina rectángulo.

La única prueba que he visto es a través de la Sala de Matrimonio Teorema.

Q: ¿Puede este resultado se demostró sin el uso de la Sala de Matrimonio del Teorema?

I. e., puede probarse sin algo que las cantidades para el uso de algo equivalente a la Sala del Matrimonio Teorema de alguna manera esencial (por ejemplo, la sustitución de "por parte del Ayuntamiento de Matrimonio Teorema" por una prueba de la Sala de Matrimonio del Teorema).

Answer 1

Que un $k$-regular bipartito gráfica tiene un perfecto maridaje (incluso un $1$-factorización) se sigue inmediatamente de las siguientes opciones:

Si $G$ es un bipartito gráfico, a continuación, $\chi^\prime(G)=\Delta(G),$

donde como de costumbre, $\chi^\prime(G)$ es el borde cromática número y $\Delta(G)$ es el máximo grado.

Prueba: Mantener adecuadamente para colorear los bordes de $G$ con los colores de la $\{1,2,\ldots,\Delta(G)\}$ el mayor tiempo posible. Supongamos que una ventaja $uv$ no puede ser correctamente los colores. Podemos modificar la existente para colorear para que nos permiten color $uv$ como sigue.

Deje $C(u)$ ser los colores que se utilizan en los bordes incidente con $u$, y del mismo modo definen $C(v)$. De curso $|C(u)|<\Delta(G)$$|C(v)|<\Delta(G)$. Por otro lado, como que no hay color disponible correctamente el color de la $uv$ tenemos $C(u)\cup C(v)=\{1,2,\ldots,\Delta(G)\}$. Los dos anteriores sentencias implica que no es un color $i\in C(u)\setminus C(v)$ y un color $j\in C(v)\setminus C(u)$.

Bien, consideremos el camino más largo $P$ a partir de a $u$ con bordes alternando entre los colores de la $i$$j$. Tenga en cuenta que $v\not\in P$ ya que de lo contrario $P\cup uv$ formaría un ciclo de longitud impar. Por lo tanto ahora podemos simplemente intercambiar los colores de la $i$ $j$ a lo largo de este camino, y luego de color $uv$ color $i$.