Scheinerman–Ullman fractional Hamiltonicity conjecture and Devriendt's resistance-positivity conjecture

Every finite graph $G=(V,E)$ that is $2$ -tough is fractionally Hamiltonian. Here, $G$ is $2$ -tough if, for every vertex set $S\subseteq V$ with $c(G-S)>1$ , one has $|S|\ge 2c(G-S)$ , where $c(G-S)$ denotes the number of connected components of $G-S$ . The graph $G$ is fractionally Hamiltonian if there exists a function $x:E\to[0,1]$ such that $\sum_{e\in E}x_e=|V|$ and, for every nonempty proper subset $S\subset V$ , $\sum_{e\in\delta(S)}x_e\ge 2$ , where $\delta(S)$ is the edge cut between $S$ and $V\setminus S$ .

References

Primary source

arXiv

Additional references

Toughness Bounds for Fractional Hamiltonicity and Resistance Positivity — arXiv

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed progress

A new paper proves the conjecture for graphs at least five times tougher than required, while the broader resistance claim has reportedly been disproved.

The Scheinerman–Ullman conjecture asks whether every $2$ -tough graph is fractionally Hamiltonian; Devriendt asked whether every $1$ -tough graph is resistance positive.

Known results

Every $10$ -tough chordal graph with at least $3$ vertices is Hamilton-connected (2015).

September 2026 developments

Toughness Bounds for Fractional Hamiltonicity and Resistance Positivity claims that every connected non-fractionally-Hamiltonian graph has a non-Hamiltonian chordal spanning supergraph; combined with the chordal theorem, this yields fractional Hamiltonicity for every $10$ -tough graph and resistance positivity in that class.
A July 2026 paper claims Devriendt’s broader resistance conjecture is false: for every $n \ge 11$ , there is an $n$ -vertex $1$ -tough graph that is not resistance nonnegative.

Current status (as of September 2026): Fractional Hamiltonicity is established for $10$ -tough graphs, but the $2$ -tough conjecture remains open; the broad $1$ -tough resistance-positivity conjecture is claimed false, while positivity for the $10$ -tough class is claimed.

Sources

No solutions have been posted yet.