Demostrar que un gráfico no tiene una correspondencia perfecta

Question

Considere el siguiente gráfico:

Encuentre una coincidencia perfecta o demuestre que no existe.

No creo que exista una coincidencia perfecta aquí, ya que los vértices $a_2, a_3$ y $a_4$ son problemáticos para nosotros, pero tengo algunos problemas para probar esto. Utilizando el teorema de Hall, podemos demostrar que un emparejamiento de una determinada cardinalidad no existe, pero ¿cómo se supone que debo saber la cardinalidad del emparejamiento perfecto para demostrar mi afirmación? ¿Puede alguien darme una pista sobre cómo aplicar el teorema en este caso?

EDITAR : ¿Puedo suponer que la cardinalidad de la coincidencia perfecta $|M| = 2$ ya que la cubierta de vértices más pequeña es { $a_5, a_4$ }, y luego encontrar dos vértices que rompan la condición de Hall?

Answer 1

Supongamos una coincidencia perfecta $M$ existe. Tenga en cuenta que $b_2$ tiene grado $2$ Así que, o bien $\{b_2,a_2\}\in M$ o $\{b_2,a_5\}\in M$ .

Caso I. $\{b_2,a_2\}\in M$ . Entonces, $\{b_3,a_5\}\in M$ . Por lo tanto, $\{b_5,a_6\}\in M$ . Ahora, $b_6$ no se puede emparejar.

Caso II. $\{b_2,a_5\}\in M$ . Por lo tanto, $\{b_5,a_6\}\in M$ . Ahora, $b_6$ no se puede emparejar.

Answer 2

Como Daniel Mathias dio la pista;

El gráfico $G$ está desconectado. Subgrafo generado por $\{a_2,b_2,b_3,a_5,a_6,b_5,b_6\}$ es un componente y subgrafo generado por $\{a_1,a_3,a_4,b_1,b_4\}$ es otro componente.

Ahora bien, si $G$ tiene una coincidencia perfecta entonces ambos componentes también tienen una coincidencia perfecta. Pero ninguno de los componentes tiene coincidencia perfecta porque cada uno tiene un número impar de vértices (Razón: Un grafo tiene coincidencia perfecta con $M$ bordes entonces necesariamente tiene $2M$ vértices).