Estoy tratando de probar que un gráfico $G$ contiene $k$ aristas independientes si $q(G-S) \le |S|+|G|-2k$ para todos los conjuntos $S \subset V(G)$ (donde $q(G-S)$ son los componentes impar). Sin embargo, tengo problemas para verificar si la siguiente dirección es correcta, así que, ¿esto parece válido para demostrar que si un gráfico contiene $k$ aristas independientes, entonces $q(G-S) \le |S|+|G|-2k$ ?
Supongamos que el gráfico $G$ con pedido $n$ contiene $k$ aristas independientes, y añadir $n-2k$ vértices que son todos adyacentes a los vértices en $G$ llamaremos a este gráfico $G'$ . Entonces, podemos encontrar una coincidencia perfecta en $G'$ haciendo coincidir cada uno de estos $n-2k$ vértices añadidos con el resto $n-2k$ vértices en $G$ que no tienen parangón. Entonces, por el teorema de Tutte, tenemos que $q(G'-S) \le |S|$ para todos $S \subset G'$ . Tome un subconjunto $S$ de $V(G)$ y también incluye todos los $n-2k$ vértices añadidos a $S$ y llamaremos a este subconjunto $S'$ . Entonces $q(G'-S') = q(G-S) \le |S'| =|S|+|G|-2k$ .
