Prueba de coincidencias en un gráfico

Question

Sea M un emparejamiento en un grafo G. Demuestre que si P es un camino alternativo para M en G que comienza y termina en vértices no coincidentes, entonces el emparejamiento M obtenido a partir de M sustituyendo las aristas de M que están en P por las aristas de P que no están en M, es un emparejamiento de G con una arista más que M.

Me cuesta mucho esta prueba, ¿alguien puede mostrarme cómo se hace esta prueba?

Gracias de antemano

Answer 1

Supongamos que actualmente hay $m$ bordes en $M$ . Por lo tanto, debe haber $2m+2$ vértices en $P$ (todos los vértices del $m$ bordes y $2$ vértices no coincidentes). Por lo tanto, debe haber $2m+1$ bordes en $P$ y cada arista conecta dos vértices de diferentes partes del grafo (por definición de camino alternativo). Ahora, consideremos $M'$ . $M' = P-M$ . Ahora tenemos que demostrar que no hay dos aristas en $M'$ tienen un vértice común (para que sea realmente una coincidencia). Es sencillo, a partir de la $2m+2$ vértices, $2$ son nuevos vértices y el resto $2m$ ya formaban parte de otra concordancia (por lo que no es posible que contengan una repetición). Así, $M'$ es también una coincidencia. El número de aristas en $M'$ son $2m+1$ (total de aristas en $P$ ) - $m$ (total de aristas en $M$ ) = $m+1$ .