Common insights into hypothetical complexity of graph problems 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.
Here are two references for the second part of your question.

The paper [1] addresses certain types of colorability of sparse graphs with given girth $g$. For every fixed $g$, they show that the associated decision problem is either trivial (every graph in the class has a coloring) or NP-complete. But determining which is the threshold value of $g$ remains a difficult open problem!
Edit: One of the considered problems is related to Jaeger's conjecture, that every planar graph of girth $4k$ admits a homomorphism to $C_{2k+1}$. It is shown in [1] that any counterexample directly provides a hardness proof. (A similar conjecture by Klostermeyer and Zhang exists for the odd-girth.) For the other problems considered in [1], there is no official conjecture, but for any guess about the correct threshold value $g$ that one can make, if proved false by a counterexample, the latter directly implies a corresponding hardness proof.

In the introduction of the above cited paper is also mentioned the following interesting result about SAT [2]. It is proved there that for every $k$, there exists a function $f(k)$ such that $(k,f(k))$-SAT (i.e. $k$-SAT where each variable occurs $f(k)$ times) is trivial, but $(k,f(k)+1)$-SAT is NP-complete. (The precise value of $f(k)$ seems unknown, although some estimate is given.)

[1] L. Esperet, M. Montassier, P. Ochem and A. Pinlou. A complexity dichotomy for the coloring of sparse graphs. Journal of Graph Theory 73:85-102, 2012. link + PDF on an author's website

[2] J. Kratochvil, P. Savicky and Zs. Tuza. One more occurrence of variables makes satisfiability jump from trivial to NP-complete. SIAM Journal on Computing 22:203-210, 1993. link