El tamaño del emparejar máximo está limitado por el tamaño de la cubierta del vértice mínimo

Question

<blockquote> <p>Probar, usando el teorema de dualidad débil de programación lineal,:</p> <p>Para cualquier grafo $G$ (no necesariamente bipartito), el tamaño de la máxima coincidencia es en la mayoría el tamaño de la cubierta del vértice mínimo.</p> </blockquote> <p>Soy un estudiante de hacer curso en combinatoria y realmente no sé dónde empezar en la prueba, porque este es un gráfico general, no uno bipartito avanzado. Así que realmente agradecería sugerencias. Gracias de antemano.</p>

Answer 1

Que $G=(V,E)$ sea un gráfico, que $M\subseteq E(G)$ ser el emparejar máximo del gráfico $G$ y sea la portada de vértice mínimo de $C\subseteq V(G)$ $G$. Puesto que los bordes de $M$ son separados en el sentido de que no hay dos comparten un punto final, cada vértice en $v\in C$ cubre a más de un borde en $M$. Así $|C|\ge |M|$.