The number and average length of subpaths in graphs

Stijn Cambie

REVIEW 3 major objections 5 minor 19 references

The number and average length of subpaths in graphs

T0 review · 3 major / 5 minor · reviewed 2026-08-28 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For every connected graph, the complete graph maximizes the average subpath length and the star minimizes it.

desk verdict A paper with one clean theorem, one plausible conjecture-buster, and a headline upper bound whose proof is parked in an unpublished preprint — worth refereeing after a revision. read the letter →

arxiv 2608.23542 v1 pith:AZGFJB5R submitted 2026-08-24 math.CO

Stijn Cambie This is my paper · ORCID

classification math.CO MSC 05C3505C3805C30

keywords averagepathlengthnumberofsubpathsextremalgraphtheorycompletestartriangle-freegraphsregular

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper studies one graph statistic: the average length of all simple paths, or subpaths, contained in a graph. It proves that among all connected graphs on $n$ vertices this average is minimized by the star $S_n$ and maximized by the complete graph $K_n$, settling the subpath analogues of long-standing questions about average subtree size. It also shows that the minimum number of subpaths in an $r$-regular graph is quadratic in the order, and that the balanced complete bipartite graph uniquely maximizes the number of subpaths among triangle-free graphs. In plain terms, the paper pinpoints where the extremes of subpath length and subpath count lie.

What carries the argument

The proof of the upper bound rests on a length-by-length ratio comparison. Writing $\operatorname{pn}_k(G)$ for the number of subpaths of length $k$, the paper asserts that for every $k\ge 1$, $$\frac{\operatorname{pn}_k(K_n)}{\operatorname{pn}_{k-1}(K_n)} \ge \frac{\operatorname{pn}_k(G)}{\operatorname{pn}_{k-1}(G)}.$$ The reason is local: a subpath of length $k-1$ with a chosen starting vertex can be extended to a subpath of length $k$ in at most $n-k$ ways, and the complete graph attains this bound for every choice. An induction on averages of path lengths truncated at $k$, analogous to the treatment in reference [5], converts these ratio inequalities into the global bound $\operatorname{avp}(G)\le\operatorname{avp}(K_n)$. The lower bound $\operatorname{avp}(G)\ge\operatorname{avp}(S_n)$ is built differently: start from a spanning tree, where the extremal inequality is standard, and argue that every added edge creates many new paths whose average length exceeds the star's.

What would settle it

A finite test: enumerate all connected graphs on six vertices, compute $\operatorname{avp}$ exactly, and compare with $\operatorname{avp}(K_6)$; any graph exceeding $K_6$ refutes the headline theorem. To probe the proof rather than the statement, formally instantiate the promised induction from the ratio inequality to the average bound and check whether its base and step hold for all $n$.

Watch

Extended reading notes

Core claim

The central claim is a pair of extremal inequalities. For every connected graph $G$ of order $n$, $$\operatorname{avp}(S_n)\le \operatorname{avp}(G)\le \operatorname{avp}(K_n),$$ where $\operatorname{avp}(H)$ is the average length of all subpaths of $H$. The inequality $\operatorname{avp}(G)\le\operatorname{avp}(K_n)$ is the headline: no graph has paths that are, on average, longer than the complete graph's paths, and the star gives the shortest average. The theorem also bundles seven structural statements: among trees the path maximizes and the star minimizes; non-isomorphic trees can share an average path length; the ratio of local to global average path length is dense in subsets of the positive reals; the vertex maximizing the local average can have any degree; every non-star tree has a 1-associate (a tree formed by deleting one edge and adding another) with smaller average path length; removing an edge or contracting an edge can increase the average; and graphs of arbitrarily large minimum degree can still have average subpath length $O(\log n)$.

Load-bearing premise

The upper bound rests on the assumption that the pattern of path counts, checked length by length, forces the overall average subpath length to be no larger than the complete graph's; the induction that would prove this implication is not written out in the paper.

Editorial extensions

If this is right

For any problem that routes or enumerates paths with length-dependent costs, the complete graph is the hardest instance: no connected graph has a larger average subpath length.
The star is the unique minimizer for average subpath length, while among trees the path gives the largest value, so trees interpolate between the two extremes.
The minimum total number of subpaths in an $r$-regular graph is $\Theta(n^2)$, so conjectured exponential lower bounds for cubic graphs fail badly.
Among triangle-free graphs, the balanced complete bipartite graph uniquely maximizes the total number of subpaths, making the extremal graph for path counting match the extremal graph for edge counting.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The per-length ratio inequality is stronger than the average inequality it is used to prove; if it holds for every $k$, it may imply that the distribution of subpath lengths in $K_n$ stochastically dominates that of every other graph, a sharper statement the paper does not explicitly make.
Theorem 2 determines that the minimum path number of $r$-regular graphs is quadratic but not the sharp constant; finding the exact leading coefficient and the extremal graphs is a natural open extension, and the paper notes they may not be unique.
The triangle-free maximum suggests a broader conjecture: for $K_r$-free graphs, the balanced complete $(r-1)$-partite graph should maximize the total number of subpaths, extending the paper's exact $r=3$ result to all $r$.

Share X Bluesky LinkedIn Reddit HN

Formalized claims in Lean

Claim #1: The central claim is a pair of extremal inequalities. For every connected graph $G$ of order $n$, $$\operatorname{avp}(S_n)\le \operatorname{avp}(G)\le \operatorname{avp}(K_n),$$ where $\operatorname{avp}(H)$ is the average length of all subpaths of $H$. The inequality $\operatorname{avp}(G)\le\operatorname{avp}(K_n)$ is the headline: no graph has paths that are, on average, longer than the comple

/-- @claim 1 The central claim is a pair of extremal inequalities. For every connected graph $G$ of order $n$, $$\operatorname{avp}(S_n)\le \operatorname{avp}(G)\le \operatorname{avp}(K_n),$$ where $\operatorname{avp}(H)$ is the average length of all subpaths of $H$. The inequality $\operatorname{avp}(G)\le\operatorname{avp}(K_n)$ is the headline: no graph has paths that are, on average, longer than the comple -/
def central_claim : Prop :=

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

Let me give you the quick version. This paper has two genuinely useful parts and one central claim that is not yet proved in the text. The clean part is Theorem 3: among triangle-free graphs, K_{⌊n/2⌋,⌈n/2⌉} uniquely maximizes the number of subpaths. The proof is self-contained and, as far as I can tell, correct. The matching-count bound m_s(G) ≤ m_s(T_n) with the Mantel-based induction is a neat argument, and the path-counting via ordered matchings checks out. This confirms a conjecture from Knor et al. and is worth having.

Theorem 2 is also interesting: it gives a quadratic lower bound on the path number in r-regular graphs, disproving a conjecture of an exponential lower bound. The construction is sketched rather than fully specified — for even r it says 'modified regular constructions work' — but the scheme is credible and the bound is right. I'd want the building blocks made explicit before trusting it fully.

The problem is the paper's headline: Theorem 1.1(8), avp(G) ≤ avp(K_n). The proof in Section 2 takes you to the ratio inequality pn_k(K_n)/pn_{k-1}(K_n) ≥ pn_k(G)/pn_{k-1}(G), then says the averaging step follows by an induction 'analogous to [5, Sec.5]'. Section 1.1 then says an updated version of [5] will contain both directions of item 8. So the main upper bound is deferred to an unpublished preprint by the same group. That is a real completeness problem; a claim in the abstract shouldn't be at the end of a citation chain to a forthcoming work.

That said, the gap is not as deep as the stress-test suggests. The ratio inequality is stronger than pointwise domination: it gives A_k/B_k nonincreasing in k, and for positive sequences that implies the weighted average with weights A_k is at most the weighted average with weights B_k. So the missing averaging argument is a standard one-liner, not a hidden trap. The paper just doesn't give it. This makes the fix easy — but until the author writes it out, the theorem is asserted, not demonstrated.

Other items in Theorem 1 are a mixed bag: item 1 is folklore; items 5 and 6 are fine sketches; the density proof in item 3 is plausible but terse. The lower bound in item 8 is also sketched, though the star-extremal claim is believable.

My recommendation: send this to a good referee, but require the proof of item 8 to appear in the manuscript (or the claim to be marked as conditional). With a short added section, this could be a solid paper. As it stands, it's a preprint with one very nice theorem, one plausible construction, and a main theorem whose proof is elsewhere.

Referee Report

3 major / 5 minor

Summary. The paper studies the number pn_k(G) of length-k paths in a connected graph and the average length avp(G) of all its subpaths. It presents Theorem 1.1 with eight claims, of which item 8 states that for every n-vertex graph G, avp(S_n) ≤ avp(G) ≤ avp(K_n), i.e., that the complete graph maximizes the average subpath length; this is the headline announced in the abstract. The paper also proves Theorem 2, asserting that among r-regular graphs of order n the minimum path number is quadratic, and Theorem 3, asserting that the balanced complete bipartite graph uniquely maximizes the number of subpaths among triangle-free graphs.

Significance. If the results are fully established, they would provide attractive answers to analogues of Jamison's questions and would settle a conjecture on the subpath number of regular graphs. The matching-and-path-counting proof of Theorem 3 is a clean argument and appears sound, and the lower-bound direction of item 8 has a plausible elementary justification. However, the upper bound of item 8, which is the central claim announced in the abstract, is not proved in this manuscript but is deferred to an unpublished companion preprint, and the construction behind Theorem 2 is not specified to a verifiable standard. The paper therefore cannot be accepted in its present form, but the core ideas are promising and a revision could close the gaps.

major comments (3)

[Section 1.1 and Section 2, proof of Theorem 1.1(8)] The upper bound avp(G) ≤ avp(K_n), which is the headline result, is not proved in this manuscript. The proof stops after deriving the ratio inequality pn_k(K_n)/pn_{k−1}(K_n) ≥ pn_k(G)/pn_{k−1}(G) and states that an induction 'analogous to [5, Sec. 5]' yields the average bound. Section 1.1 explicitly says that an updated version of [5] will contain both directions of item 8. This is a load-bearing omission: the ratio inequality alone gives only pointwise count domination pn_k(G) ≤ pn_k(K_n), which does not by itself imply domination of the weighted averages avp = Σ k pn_k / Σ pn_k because the denominator Σ pn_k can differ between G and K_n. The missing averaging argument is the core of the theorem, and [5] is an unpublished preprint of the same research group. The manuscript is therefore not self-contained for its central claim.
[Section 3, Theorem 2] The construction proving the quadratic upper bound is not rigorously specified. The proof begins by taking floor(n/(r+2)) 'small graphs with total order n' each having one vertex of degree r−2 and all others of degree r, but the existence of such blocks is not established; for r=3 the smallest simple graph with degree sequence (3,3,3,1) has order 6, so the stated number of blocks is incompatible with a total of n vertices. The connecting structure is also described only informally: for even r the proof says 'modified regular constructions work as well' without giving them, and for odd r the replacement of the cycle by a tree is not specified, despite the fact that a tree does not add 2 to every connector as a cycle does. Because these blocks and connections are the vehicle for the O(n^2) path bound, the proof of Theorem 2 cannot be verified as written.
[Section 2, proof of Theorem 1.1(6)] The proof of item 6 compares the wrong objects. For the contraction claim, it says avp(G,v)∼n/4 while avp(P_{n−1})∼n/3, but avp(G,v) is the average length of paths containing the pendent vertex v, not the global avp(G). A direct computation for G = P_{n−1} with a leaf v attached to a central vertex c gives avp(G) = (W(P_{n−1}) + Σ_x(dist(c,x)+1))/C(n+1,2) ∼ n/3 + 1/6, whereas avp(P_{n−1})∼ n/3 − 2/3; hence the claimed increase is true, but the stated local-to-global inference is invalid. The edge-deletion part is asserted without a calculation.

minor comments (5)

[Section 2, proof of Theorem 1.1(3)] The density claims in R_+ and (1/2,∞) are only sketched; the phrase 'varying the ratios will result in density results' should be replaced by an explicit argument showing that the limiting values cover the stated intervals.
[Section 2, proof of Theorem 1.1(7)] The construction of graphs with δ(G)≥r and avp(G)=O(log n) is a one-sentence sketch; please provide a precise construction, including the even-r case, and the O(log n) calculation.
[Section 2, notation] The overline distinguishing avp from its reduced version disappears in several places; for example, the sentence 'avp(T)=µ(T) and avp(T)=W(T)/C(n+1,2)' appears to conflate the two notions. Please typeset the notation consistently.
[Section 3, Theorem 2] The graph6 string for the Pappus graph contains '?' characters and is not a valid graph6 code; please replace it with a correct string or a drawing.
[Section 2, proof of Theorem 1.1(8)] The assertion that 'every additional edge implies at least n paths are added' should be justified; the current sentence is too terse for a rigorous inductive step in the lower-bound proof.

Circularity Check

1 steps flagged · score 5.0 of 10

The headline upper bound avp(G) ≤ avp(K_n) is not proved in the paper; its final averaging step is deferred to the authors' own unpublished/forthcoming work [5], making the central claim rest on a load-bearing self-citation.

self citation load bearing [Section 1.1 and proof of Theorem 1.1, item 8 (upper bound)]
"From this, one can (e.g. by proving the inequality inductively on the average of path lengths bounded by a certain k) derive that avp(G)≤avp(K n). The latter is analogous to [5, Sec. 5], where the implications are written down in more detail. // In particular, an updated version of [5] will contain both directions of the initial version of item 8 in Theorem 1."

The upper bound is the paper's headline claim. The proof stops after the ratio observation pn_k(K_n)/pn_{k-1}(K_n) ≥ pn_k(G)/pn_{k-1}(G), and the essential step from this ratio bound to avp(G)≤avp(K_n) is asserted with 'one can derive' and referred to [5, Sec. 5]. [5] is an unpublished preprint by the same authors, and the manuscript itself states that an updated [5] will contain both directions of item 8. Thus the central result is not derived in this paper; its proof is delegated to a self-cited future version. The pointwise ratio inequality alone does not imply the avp comparison, since avp = Σ k·pn_k / Σ pn_k depends also on the denominator; no independent derivation of the averaging step is supplied. This is a load-bearing self-citation rather than a self-contained proof.

full rationale

The paper is not fully circular in the definitional sense: the lower bound in item 8 is argued within the paper by a spanning-tree edge-adding induction; the ratio observation for K_n is an independent intermediate statement; and Theorem 3 on triangle-free graphs is proved self-containedly via matchings, Mantel's theorem, and path-counting inequalities. However, the manuscript's headline upper bound avp(G)≤avp(K_n) is not actually proved. The proof of item 8 says the averaging step can be derived by an induction 'analogous to [5, Sec. 5]', and Section 1.1 explicitly says that an updated version of [5]—an arXiv preprint by the same authors—will contain both directions of item 8. Since [5] is not presented as machine-checked, code-reproduced, or otherwise externally verified, this is a load-bearing self-citation for the paper's central claim. The paper also flags this incompleteness itself in Section 1.1, which is why the score is substantial but not maximal: the gap is a deferred proof rather than an exact equation equating the result to its inputs, and the independent ratio inequality and the self-contained proof of Theorem 3 provide genuine partial content.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claims rest on standard external theorems (Mantel, average-distance bounds) plus two paper-specific assumptions: the existence of degree-prescribed building blocks in Theorem 2, and the unproved averaging induction from the author's preprint [5] that underpins the headline upper bound of item 8.

assumptions (5)

standard math Mantel's theorem: a triangle-free graph of order n has at most floor(n^2/4) edges
Used to bound e(G) in the matching induction in Theorem 3.
standard math Folklore result on average distance in trees: µ(S_n) ≤ µ(T) ≤ µ(P_n)
Used directly in item 1 of Theorem 1.1 and implicitly in the lower bound of item 8.
standard math Bound (n-1)σ(v) ≥ W(G) for all vertices v, from [10, Thm. 2.1] and [3, Lem. 26]
Used in item 3 to prove the lower bound on avp(T,v)/avp(T).
ad hoc to paper Sufficiency of the ratio condition for the average bound, as claimed in [5, Sec. 5]
The proof of item 8's upper bound in this paper stops at the ratio observation and relies on [5] for the averaging induction; this is not proved here and is load-bearing.
domain assumption Existence of small graphs with all vertices degree r except one of degree r-2, for use as blocks in Theorem 2
Asserted in the proof of Theorem 2 without proof; plausibly true for all r but not demonstrated.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The number and average length of subpaths in graphs." pith.science (2026). https://pith.science/paper/AZGFJB5R

@misc{pith2026260823542,
  author       = {Pith},
  title        = {Pith review of: The number and average length of subpaths in graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AZGFJB5R}},
  note         = {Machine review of arXiv:2608.23542}
}

abstract

We study extremal questions on the average length and the number of subpaths in a graph. In particular, we prove the questions of Jamison (from $1983, 1984$) for the analogous concept of the average length of a subpath. Among other results, we prove that $K_n$ maximizes the average path length.

Figures

Figures reproduced from arXiv: 2608.23542 by the authors.

**Figure 1.** A graph with avp(G) = n − o(n) and avp(G, v) = o(n) 4. A broom shows that degree 1 is possible. For degree b + 2 at least 2, take a path P3, connect each of its endvertices with a additional vertices and the central vertex with b additional vertices, to obtain a caterpillar of order 2a + b + 3. If a ≫ b, the central vertex is the one maximizing the local average path length. 3 [PITH_FULL_IMAGE:figures/full_fig_p003… view at source ↗

**Figure 2.** A graph where the maximum local average path length [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

**Figure 3.** Example of constructed cubic and quartic graphs with low average path length and [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 16 canonical work pages

[5]

On the extrema of the mean subtree order of graphs

S. Cambie, J. Jooken, and S. Wagner. On the extrema of the mean subtree order of graphs. arXiv preprint arXiv:2508.20593, 2025

work page Pith review arXiv 2025
[1]

Adler, N

I. Adler, N. Alon, and S. M. Ross. On the maximum number of Hamiltonian paths in tournaments.Random Struct. Algorithms, 18(3):291–296, 2001

work page 2001
[2]

O. D. Byer. Maximum number of 3-paths in a graph.Ars Comb., 61:73–79, 2001

work page 2001
[3]

Cambie and Y

S. Cambie and Y. Dong. On the main distance-based entropies: the eccentricity- and Wiener-entropy.Ars Math. Contemp., 26(1):21, 2026. Id/No 6

work page 2026
[4]

Cambie, J

S. Cambie, J. Jooken, and J. Goedgebeur. The maximum number of connected sets in regular graphs.Electron. J. Comb., 32(1):research paper p1.20, 22, 2025

work page 2025
[6]

Carlson, W

E. Carlson, W. Fletcher, M. Montee, C. Nguyen, J. Renders, and X. Zhang. Graphs with many Hamiltonian paths.Involve, 18(4):613–627, 2025

work page 2025
[7]

A. J. Chin, G. Gordon, K. J. MacPhee, and C. Vincent. Subtrees of graphs.J. Graph Theory, 89(4):413–438, 2018

2018
[8]

D. Gerbner. Paths are Turán-good.Graphs Comb., 39(3):4, 2023. Id/No 56

work page 2023

Show all 19 references

[9]

Grzesik, E

A. Grzesik, E. Győri, A. Paulos, N. Salia, C. Tompkins, and O. Zamora. The maximum number of paths of length three in a planar graph.J. Graph Theory, 101(3):493–510, 2022

2022
[10]

Hua and K

H. Hua and K. C. Das. Proof of conjectures on remoteness and proximity in graphs.Discrete Appl. Math., 171:72–80, 2014

2014
[11]

R. E. Jamison. On the average number of nodes in a subtree of a tree.J. Combin. Theory Ser. B, 35(3):207–223, 1983

1983
[12]

R. E. Jamison. Monotonicity of the mean order of subtrees.J. Combin. Theory Ser. B, 37(1):70–78, 1984

1984
[13]

M. Knor, J. Sedlar, R. Škrekovski, and Y. Yang. Invitation to the subpath number.Appl. Math. Comput., 509:11, 2026. Id/No 129646

2026
[14]

L. Lovász. Random walks on graphs: A survey. InCombinatorics, Paul Erdős is eighty. Vol. 2, pages 353–397. Budapest: János Bolyai Mathematical Society, 1996

1996
[15]

D. W. Matula. On the number of subtrees of a symmetricn-ary tree.SIAM J. Appl. Math., 18:688–703, 1970

1970
[16]

L. A. Székely and H. Wang. On subtrees of trees.Adv. Appl. Math., 34(1):138–155, 2005

2005
[17]

Van Mieghem

P. Van Mieghem. Paths in the simple random graph and the Waxman graph.Probab. Eng. Inf. Sci., 15(4):535–555, 2001

2001
[18]

A. Vince. The average size of a connected vertex set of a graph—explicit formulas and open problem.J. Graph Theory, 97(1):82–103, 2021

2021
[19]

Wagner and H

S. Wagner and H. Wang. Indistinguishable trees and graphs.Graphs Comb., 30(6):1593–1605, 2014. 7

2014

Pith tools

Reviewed August 28, 2026 · model on record in the stance chip above.

[1] [5]

On the extrema of the mean subtree order of graphs

S. Cambie, J. Jooken, and S. Wagner. On the extrema of the mean subtree order of graphs. arXiv preprint arXiv:2508.20593, 2025

work page Pith review arXiv 2025

[2] [1]

Adler, N

I. Adler, N. Alon, and S. M. Ross. On the maximum number of Hamiltonian paths in tournaments.Random Struct. Algorithms, 18(3):291–296, 2001

work page 2001

[3] [2]

O. D. Byer. Maximum number of 3-paths in a graph.Ars Comb., 61:73–79, 2001

work page 2001

[4] [3]

Cambie and Y

S. Cambie and Y. Dong. On the main distance-based entropies: the eccentricity- and Wiener-entropy.Ars Math. Contemp., 26(1):21, 2026. Id/No 6

work page 2026

[5] [4]

Cambie, J

S. Cambie, J. Jooken, and J. Goedgebeur. The maximum number of connected sets in regular graphs.Electron. J. Comb., 32(1):research paper p1.20, 22, 2025

work page 2025

[6] [6]

Carlson, W

E. Carlson, W. Fletcher, M. Montee, C. Nguyen, J. Renders, and X. Zhang. Graphs with many Hamiltonian paths.Involve, 18(4):613–627, 2025

work page 2025

[7] [7]

A. J. Chin, G. Gordon, K. J. MacPhee, and C. Vincent. Subtrees of graphs.J. Graph Theory, 89(4):413–438, 2018

2018

[8] [8]

D. Gerbner. Paths are Turán-good.Graphs Comb., 39(3):4, 2023. Id/No 56

work page 2023