Círculos Impares y bordes doblemente cubiertos

Question

Dejemos que $G= (V,E)$ sea un grafo simple y no dirigido. Un conjunto $C\subseteq V$ se dice que es un cubierta del borde si para todo $e\in E$ tenemos $e\cap C \neq \emptyset$ .

Es muy satisfactorio encontrar una cubierta de borde $C$ tal que cada arista se cubre exactamente una vez (es decir, $|C\cap e| = 1$ para todos $e\in E$ ) - pero lamentablemente esto sólo es posible si $G$ no contiene círculos Impares (es decir $\chi(G) \leq 2$ ).

Sin embargo: dado cualquier gráfico $G$ ¿es siempre posible encontrar una cubierta de borde $C\subseteq V(G)$ tal que el número de aristas $e\in E$ con $e\subseteq C$ es como máximo el número de círculos Impares en $G$ ?

Answer 1

Consideremos un prisma triangular con $6$ vértices y $9$ bordes. Tienes que elegir dos vértices de cada triángulo y eso también elige los dos extremos de otra arista. Eso es un problema si lo ves como dos ciclos Impares (los triángulos. ) Supongo que hay 8 ciclos Impares si incluyes el $5$ -ciclos.

Por supuesto, con $n$ aristas todas en un vértice se puede obtener una cobertura de aristas satisfactoria utilizando $1$ vértice y otro utilizando $n$ vértices.

Del mismo modo, hay muchos conjuntos (de tamaño) diferentes $D$ de aristas que incluyen al menos una de cada ciclo impar. Para cada uno de ellos existe una cubierta de aristas que utiliza los dos vértices de cada arista en $D$ pero sólo un vértice de cada una de las otras aristas (excepto las que tienen ambos extremos también en aristas en $D$ )

MÁS TARDE

En realidad es algo más complicado que eso. Y la pregunta original sigue sin respuesta. He reformulado la pregunta con algunas variaciones aquí .