pith. sign in

arxiv: 2604.24137 · v1 · submitted 2026-04-27 · 🧮 math.CO

The minimum number of detours in a connected graph of minimum degree three

Xining Liu , Pu Qiao , Xingzhi Zhan This is my paper

Pith reviewed 2026-05-08 02:36 UTC · model grok-4.3

classification 🧮 math.CO
keywords longest pathsdetoursminimum degreeconnected graphsgraph theory
0
0 comments X

The pith

Every connected graph with minimum degree three and 18 or more vertices contains at least 36 longest paths.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper determines the smallest possible number of longest paths, called detours, in connected graphs with a given minimum degree and number of vertices. For graphs where every vertex has degree at least three, this minimum number reaches exactly 36 once there are 18 vertices, and stays at that value for all larger sizes. The authors achieve this by building specific graphs that have precisely 36 such paths and proving through detailed examination that fewer cannot occur. They also provide an upper bound on this minimum for higher degrees and a bound when the number of paths must be odd.

Core claim

We prove that a(3,n) = 36 for n ≥ 18. This is shown by exhibiting connected 3-regular graphs on n vertices with exactly 36 detours for each such n, combined with a case analysis demonstrating that every connected graph of minimum degree 3 on at least 18 vertices has at least 36 detours. Additionally, we establish that a(k,n) ≤ (k!)^2 for n ≥ k² + 2k + 3 and b(3,n) ≤ 225 for n ≥ 11.

What carries the argument

The quantity a(k,n), defined as the minimum number of detours (longest paths) over all connected graphs with minimum degree k and n vertices. The proofs use explicit graph constructions to achieve the bound and exhaustive case analysis on the structure of longest paths to show minimality.

Load-bearing premise

The case analysis exhaustively covers all ways longest paths can be arranged in a minimum-degree-3 graph without overlooking a configuration that has fewer than 36 such paths.

What would settle it

A counterexample would be any connected graph with minimum degree 3 on 18 or more vertices that has only 35 or fewer longest paths.

Figures

Figures reproduced from arXiv: 2604.24137 by Pu Qiao, Xingzhi Zhan, Xining Liu.

Figure 1
Figure 1. Figure 1: Parallel chords and crossing chords Observe that in the parallel case, θ(e) contains the path xt −→C xs and in the crossing case, θ(e) contains the path xs −→C xt . It is possible that for e1, e2 ∈ E(C) with e1 6= e2, we have γ(e1) = γ(e2). But in that case we still have θ(e1) 6= θ(e2). Thus the n edges of C yield n pairwise distinct detours. Altogether, G contains at least 3n ≥ 36 detours. Case 3. n = 11.… view at source ↗
Figure 2
Figure 2. Figure 2: The Wujing graph H For a pair i, j ∈ {1, 2, 3} with i 6= j, let k ∈ {1, 2, 3}\{i, j}. There exist a (ui , vj )-detour A (1) i,j = Pi ∪ Pk ∪ ukuj ∪ Pj [uj , vj ] and a (wi , vj )-detour A (2) i,j = Pi [wi , x] ∪ Pk ∪ ukui ∪ uiuj ∪ Pj [uj , vj ]. Since G is nonhamiltonian and for i 6= j there exists a (wi , vj )-detour, by Fact 2 we deduce that wi and vj are nonadjacent. Clearly the 12 detours A (p) i,j , p … view at source ↗
Figure 3
Figure 3. Figure 3: The θ-graph Q Let i, j ∈ {1, 2, 3} with i 6= j and let k ∈ {1, 2, 3} \ {i, j}. If ui and uj are adjacent, then H1 , Pi [ui , y] ∪ Pj [uj , y] ∪ Pk ∪ {xui , xuj , uiuj} is a Wujing graph. If vi and vj are adjacent, then H2 , Pi [vi , x] ∪ Pj [vj , x] ∪ Pk ∪ {yvi , yvj , vivj} is a Wujing graph. Since V (H1) = V (H2) = V (Q) and H1, H2, Q are traceable, by Lemma 2, we have f(G) ≥ 36. Next we assume that ui a… view at source ↗
Figure 4
Figure 4. Figure 4: Add K4 to the vertex v Definition 6. Adding the complete graph Kn to an edge e of a graph is the operation of first subdividing e using a new vertex v and then identifying v with a vertex of Kn. The operation of adding K4 to an edge is depicted in view at source ↗
Figure 5
Figure 5. Figure 5: Add K4 to the edge xy G7, G8, G12, G15 and G16 are depicted in (a), (b), (c), (d) and (e) of view at source ↗
Figure 6
Figure 6. Figure 6: The graphs G7, G8, G12, G15 and G16 For every integer n ≥ 18, there exist nonnegative integers p and q with 0 ≤ q ≤ 2 satisfying n = 12 + 3p+ 4q. Observe that the graph G12 has a unique central vertex which we denote by v. Let the two neighbors of v with degree four in G12 be x and y. If q = 0, Gn is obtained from G12 by successively adding K4 to v p times; if q = 1, Gn is obtained from G12 by successively… view at source ↗
Figure 7
Figure 7. Figure 7: The graph G29 satisfying f(Mn) = (k!)2 . For n = 2k + 1, Mn is the graph obtained by identifying a vertex of a copy of Kk+1 with a vertex of another copy of Kk+1. For n = 2k + 2, Mn is the graph obtained by adding an edge to join a vertex of a copy of Kk+1 and a vertex of another copy of Kk+1. For n = 3k + 3, Mn is the graph obtained by adding Kk+1 to the cut-edge of M2k+2. Next suppose n = 3k + 3+pk +q(k … view at source ↗
Figure 8
Figure 8. Figure 8: The graph M24 for k = 4 Corollary 9. Let a(k, n) denote the minimum number of detours in a connected graph of minimum degree k and order n with k ≥ 4. If n ≥ k 2 + 2k + 3, then a(k, n) ≤ (k!)2 . Proof. Since n ≥ k 2 + 2k + 3 = 3k + 3 + k(k − 1), by Theorem 8 it suffices to show that for every integer f with f ≥ k(k − 1), there exist nonnegative integers p and q such that f = pk + q(k + 1). Let f = sk + r w… view at source ↗
Figure 9
Figure 9. Figure 9: The graphs R11, R12 and R13 Next suppose n ≥ 14. If n ≡ 2 mod 3, then Rn is obtained from R11 by successively adding K4 to the cut-vertex; if n ≡ 0 mod 3, then Rn is obtained from R12 by successively adding K4 to the cut-vertex; if n ≡ 1 mod 3, then Rn is obtained from R13 by successively adding K4 to the cut-vertex. We need only to verify that each of the three graphs R11, R12 and R13 has exactly 225 deto… view at source ↗
Figure 10
Figure 10. Figure 10: The graphs H5, H6 and H7 Next suppose n ≥ 8. Let x and y be the two nonneighbors of v in H7. We define Hn to be the graph obtained by subdividing the edge xy with vertices z1, z2, . . . , zn−7 and joining v and zi for i = 1, 2, . . . , n − 7. Then it is easy to verify that v is an endpoint of exactly eight detours of Hn. The graph H10 is depicted in view at source ↗
Figure 11
Figure 11. Figure 11: The graph H10 Problem 6 (X. Zhan, February 2026). Let k and n be integers with 3 ≤ k ≤ n−2 and denote by q(k, n) the minimum number of detours in a hamiltonian graph of minimum degree k and order n. Determine q(k, n). Acknowledgement. This research was supported by the NSFC grant 12271170 and Science and Technology Commission of Shanghai Municipality grant 22DZ2229014. 19 view at source ↗
read the original abstract

A longest path in a graph is called a detour. Denote by $a(k,n)$ the minimum number of detours in a connected graph with minimum degree $k$ and order $n,$ and denote by $b(k,n)$ the minimum odd number of detours in such a graph. X. Zhan has posed the problem of determining $a(k,n)$ and $b(k,n).$ It is known that $a(2,n)=4$ for $n\ge 4$ and $b(2,n)=9$ for $n\ge 9.$ In this paper we prove that $a(3,n)=36$ for $n\ge 18,$ $a(k,n)\le (k!)^2$ for $n\ge k^2+2k+3$ and $b(3,n)\le 225$ for $n\ge 11.$ We also pose several related unsolved problems.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper proves that a(3,n), the minimum number of detours in a connected graph of minimum degree 3 on n vertices, equals 36 for all n ≥ 18. It also establishes the general upper bound a(k,n) ≤ (k!)^2 for n ≥ k² + 2k + 3 and shows that b(3,n) ≤ 225 for n ≥ 11, where b(k,n) is the minimum odd number of detours. The results rely on explicit constructions achieving the stated upper bounds together with a case analysis establishing the matching lower bound for a(3,n).

Significance. If the proofs are correct, the work resolves Zhan's problem exactly for minimum degree 3 by supplying both constructions that attain exactly 36 detours and a direct case analysis for the lower bound. The explicit constructions and the parameter-free general bound a(k,n) ≤ (k!)^2 constitute concrete, falsifiable contributions to the study of detour numbers in graphs of prescribed minimum degree.

minor comments (2)
  1. A small illustrative figure or example graph realizing 36 detours would help readers visualize the construction used for the upper bound on a(3,n).
  2. In the introduction, briefly recall the precise definition of a detour (a longest path) to ensure the paper is self-contained for readers unfamiliar with the prior literature on the problem.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work and for recommending acceptance. The recognition that the explicit constructions and the parameter-free bound a(k,n) ≤ (k!)^2 are concrete contributions is appreciated.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation consists of explicit constructions of connected minimum-degree-3 graphs with exactly 36 detours for n≥18, together with a direct case analysis establishing the matching lower bound. The general upper bounds a(k,n)≤(k!)^2 and b(3,n)≤225 are proved by explicit constructions without fitted parameters or self-referential definitions. The introductory reference to Zhan posing the problem is not load-bearing in any proof step and does not reduce any claimed equality or bound to an input by construction. No self-citation chain, ansatz smuggling, or renaming of known results appears in the argument structure.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard graph-theoretic definitions of paths, longest paths, connectivity, and minimum degree, plus the existence of particular constructions that realize the stated minima.

axioms (1)
  • standard math Standard definitions and basic properties of paths and degrees in undirected graphs
    The paper invokes the usual notions of path, longest path, connected graph, and minimum degree without re-proving them.

pith-pipeline@v0.9.0 · 5459 in / 1252 out tokens · 26721 ms · 2026-05-08T02:36:24.112355+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

10 extracted references · 10 canonical work pages

  1. [1]

    Beineke, J.E

    L.W. Beineke, J.E. Dunbar and M. Frick, Detour-saturated grap hs, J. Graph Theory, 49(2005), 116–134

    work page 2005

  2. [2]

    Bollob´ as and A

    B. Bollob´ as and A. Sarkar, Paths of length four, Discrete Math ., 265(2003), 357–363

    work page 2003

  3. [3]

    Bondy and U.S.R

    J.A. Bondy and U.S.R. Murty, Graph Theory, GTM 244, Springer, N ew York, 2008

    work page 2008

  4. [4]

    Brinkmann and M

    G. Brinkmann and M. De Pauw, Uniquely hamiltonian graphs for many sets of degrees, Discrete Math. Theor. Comput. Sci., 26(2024), no.3, Pa per No.7

    work page 2024

  5. [5]

    Chartrand, G.L

    G. Chartrand, G.L. Johns and S.L. Tian, Detour distance in graph s, Quo vadis, graph theory?, 127–136, Ann. Discrete Math., 55, North-Holland , Amsterdam, 1993

    work page 1993

  6. [6]

    Erd˝ os and G

    P. Erd˝ os and G. Katona (eds), Theory of Graphs, Proceeding s of the colloquium held at Tihany, Hungary, September 1966, Academic Press, New York, Problem 4, p.362, 1968

    work page 1966

  7. [7]

    Fleischner, Uniquely Hamiltonian graphs of minimum degree 4, J

    H. Fleischner, Uniquely Hamiltonian graphs of minimum degree 4, J. G raph Theory, 75(2014), no.2, 167–177

    work page 2014

  8. [8]

    Kapoor, H.V

    S.F. Kapoor, H.V. Kronk and D.R. Lick, On detours in graphs, Cana d. Math. Bull., 11(1968), 195–201

    work page 1968

  9. [9]

    West, Introduction to Graph Theory, Prentice Hall, Inc., 19 96

    D.B. West, Introduction to Graph Theory, Prentice Hall, Inc., 19 96

    work page

  10. [10]

    Zhan, The minimum number of detours in graphs, Australas

    X. Zhan, The minimum number of detours in graphs, Australas. J . Combin., 90(2024), 85–93. 20

    work page 2024