**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>



Two from cubic subgraph hardness
A formal proof has been produced.
See <https://arxiv.org/abs/2105.07161>


