**The Problem**

For a given graph $G$, the cubic subgraph problem asks if there is a subgraph where every vertex has degree 3. The cubic subgraph problem is NP-hard even in bipartite planar graphs with maximum degree at most 4.

Suppose we have an oracle that decides if a bipartite graph contains a "two from cubic subgraph". Can we solve the cubic subgraph problem in polynomial time?

Here "two from cubic" means every vertex is of degree 3 except for two degree 2 vertices.

I would also be happy if there was another way to (dis)prove that two from cubic subgraph is NP-hard.

**Some Remarks**

One variant I explored is if we are allowed to pick which of the two vertices have degree 2. Then for a given graph $G$ and $uv\in E(G)$, we can ask if $G-uv$ has a two from cubic subgraph with special vertices $u, v$ to solve the cubic subgraph problem. This variant is thus NP-hard. However, I have been unable to find a reduction for the original problem.

One other thing to note is that given a two from cubic subgraph oracle, it is pretty easy to find a two from cubic subgraph: While there is a vertex $v$ such that $G-v$ has a two from cubic subgraph, delete $v$.

We could also relax the restrictions on the problem. For example, is the two from 4-regular subgraph problem NP-hard? Two from 4-regular means every vertex has degree 4 except for two vertices of degree 3. Even any useful facts about two from cubic subgraph or two from 4-regular graphs would be appreciated.

Finally, this point might be a bit off-topic, but we could potentially phrase this as a graph editing problem. "Is there a sequence of edges/vertex deletions leading to a two from cubic subgraph?" I am not familiar with these types of questions but thought it could be an interesting approach.

crossposted from https://math.stackexchange.com/questions/3867470/two-from-cubic-subgraph-hardness