Consider the graph $G$, which is comprised of 2 vertex disjoint odd cycles ($C_1$, $C_2$) where $|C_1|$ and $|C_2| geq 5$. $G$ is sub-cubic and connected, with edges in between the cycles. Because $G$ is sub-cubic, each node’s degree $leq 3$ but $geq 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:

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

We know that for either cycle $C$, $MinVC = leftlfloorfrac{|C|+1}{2}rightrfloor$. Thus, $MinVC(G) geq leftlfloorfrac{|C_1|+1}{2}rightrfloor+leftlfloorfrac{|C_2|+1}{2}rightrfloor$

A loose upper bound would be to take all vertices of one cycle and solve optimally for the other. Thus, $MinVC(G) leq min(|C_1|,|C_2|) + leftlfloorfrac{max(|C_1|, |C_2|)+1}{2}rightrfloor$.