5/4 n TSP walk bound for subcubic graphs

Conjecture 1 · arXiv:1608.07568

arXiv Conjecture high confidence— first stated 2016-09-05

Authors: Zdenek Dvorak, Daniel Kral, Bojan Mohar

Status solved high confidence

The conjecture is fully resolved. Wigal, Yoo, and Yu (arXiv:2112.06278, December 2021) prove that every simple 2-connected subcubic graph on n vertices with n_2 vertices of degree two has a TSP walk of length at most (5n+n_2)/4 - 1, confirming Conjecture 1 of Dvořák, Král', and Mohar. The bound is shown to be tight, and they also provide a quadratic-time combinatorial algorithm, yielding a 5/4-approximation for the graphic TSP on cubic graphs (improving the prior 9/7 ratio). The result was subsequently published in the Journal of Combinatorial Theory, Series B.

Cited literature (1)

proof Approximating TSP walks in subcubic graphs (2021)

Wigal, Michael C.; Yoo, Youngho; Yu, Xingxing · Journal of Combinatorial Theory, Series B · arXiv:2112.06278

Proves the full conjecture: every simple 2-connected subcubic n-vertex graph with n_2 degree-two vertices has a TSP walk of length at most (5n+n_2)/4 - 1, characterizes extremal graphs, and gives a quadratic-time algorithm.

Reviewer notes. arXiv:2112.06278 (Wigal, Yoo, Yu, December 2021) explicitly confirms this conjecture and states the bound is best possible, matching both extremal constructions (Proposition 29 and 31) from the source paper. The ScienceDirect page (pii/S0095895622000879, ISSN 0095-8956 = JCTB) confirmed journal publication but returned HTTP 403 so the DOI could not be retrieved; venue identified from ISSN prefix.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. Every 2-connected subcubic $n$-vertex graph with $n_2$ vertices of degree two has a TSP walk of length at most $\frac{5}{4}n + \frac{1}{4}n_2 - 1$.

Context

The authors construct a 2-connected cubic $n$-vertex graph with no TSP walk shorter than $\frac{5}{4}n - 2$ (Proposition 31) and a 2-connected subcubic $n$-vertex graph with $n_2 = \Theta(n)$ degree-two vertices and no TSP walk shorter than $\frac{5}{4}n_2 - 1$ (Proposition 29); the cubic construction was found independently by Maz\'ak and Lukot'ka. The authors believe these two constructions are tight and that the conjecture represents the correct improvement of Theorem 1 (which achieves the weaker bound $\frac{9}{7}n + \frac{2}{7}n_2 - 1$). They also remark that the stronger form of their reduction inequality (equation (1)) was kept precisely because it may be useful in an eventual proof of this conjecture.

Notes. PDF source — 'n2' in the extracted text consistently denotes $n_2$, the number of degree-two vertices, as defined throughout the paper. The phrase 'with n2 vertices of degree' in the raw extraction is a truncation of 'degree two'. The conjecture is explicitly marked as a labelled environment.

Source paper

Graphic TSP in cubic graphs
Zdenek Dvorak, Daniel Kral, Bojan Mohar · 2016-09-05
https://arxiv.org/abs/1608.07568 PDF source