I came across two examples of hypothetical hardness of some graph problems. Hypothetical hardness means that refuting some conjecture would imply the NP-completeness of the respective graph problem. For instance, Barnette's conjecture states that every 3-connected cubic planar bipartite graph is Hamiltonian. Feder and Subi proved that refuting the conjecture would imply the NP-completeness of the Hamiltonian cycle problem on graphs in the class of the conjecture.
Tutte's 5-flow Conjecture states that every bridgeless graph has a nowhere-zero 5-flow. Kochol showed that if the conjecture is false, then the problem of determining whether a cubic graph admits a nowhere-zero 5-flow is NP-complete.
Are there common insights into the above conjectures that explain the hypothetical NP-completeness of the corresponding graph problems? Are there other examples of hypothetical complexity in the above sense?
P.S. This was posted on MathoverFlow without getting an answer.