Hola
Demuestre que si removemos dos esquinas opuestas en un tablero de ajedrez de \( 8\times 8 \) obtenemos un subtablero que no puede ser cubierto por fichas rectangulares de tamaño \( 2\times 1 \) y \( 1\times 2. \) ¿Podria extender el argumento para hacer una afirmacion que aplique a todos los grafos bipartitos?
El problema se puede ver como un grafo bipartito donde los vértices son las casillas repartidas en blancas y negras (esa es la partición del grafo bipartito).
Las aristas son las fichas descritas que unen siempre vértices (casillas) blancos con negros.
El problema de cubrir el tablero con tales fichas es el problema de encontrar un "perfect matching" es decir una colección de aristas disjuntas (sin vértices en común) que cubran todos los vértices.
Pues bien en un grafo bipartito para que pueda existir un "perfect mathcing" los dos subconjuntos de vértices de la partición deben de tener el mismo número de elementos, ya que cada arista une un vértice de cada conjunto.
El argumento de Abdulai: si retiramos las casillas de los extremos, como son del mismo color, el grafo bipartito tiene \( 30 \) vértices en un conjunto de la partición y \( 32 \) en el otro, luego no puede existir un "perfect matching".
Saludos.
