Minimum Vertex Cover of 2 vertex disjoint but connected odd cycles.

Question

Consider the graph G, which is comprised of 2 vertex disjoint odd cycles (C1, C2) where |C1| & |C2| >= 5. G is sub-cubic and connected, with edges in between the cycles. Because G is sub-cubic, each node's degree <=3 but >=2.

I am interested to know whether the minimum vertex cover of G can be found in polynomial time? Furthermore, I am also interested to know whether we can:

1. Establish a tight upper bound on the MinVC for such a graph.
2. Say anything else about this graph that's insightful.

We know that for either cycle C, minVC = (|C|+1)/2. Thus, minVC(G) >= (|C1|+1)/2 + (|C2|+1)/2

A loose upper bound would be to take all vertices of one cycle and solve optimally for the other. Thus, minVC(G) <= min(|C1|,|C2|) + (max(|C1|, |C2|)+1)/2.

Answer 1

The minimum vertex cover of a disconnected graph is trivially the union of the minimum vertex covers of the components.