pith. sign in

arxiv: 1906.09197 · v1 · pith:BLQXYF2Nnew · submitted 2019-06-21 · 🧮 math.CO

Fat-triangle linkage and kite-linked graphs

Runrun Liu , Martin Rolek , Gexin Yu This is my paper

Pith reviewed 2026-05-25 18:48 UTC · model grok-4.3

classification 🧮 math.CO
keywords H-linked graphsfat-trianglekiteconnectivitysubdivisiongraph linkage
0
0 comments X

The pith

Any k-connected graph is F_k-linked for a connected k-fat-triangle, and every 8-connected graph is kite-linked.

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

The paper examines how much connectivity a graph needs to guarantee it contains a subdivision of a given multigraph H whenever the vertices of H are mapped injectively into the graph. For the k-fat-triangle, a multigraph on three vertices with exactly k edges, the authors show that k-connectivity is enough whenever the multigraph is connected. They then use this result to prove that 8-connectivity forces a graph to be kite-linked, where the kite is the graph obtained from K4 by deleting two edges at one vertex, thereby bounding the connectivity threshold for kite-linkage between 7 and 8.

Core claim

A graph G is H-linked if every injective map from the vertices of the multigraph H into G extends to an H-subdivision in G. The central result is that every k-connected graph is F_k-linked when F_k is a connected k-fat-triangle. As a direct application, every 8-connected graph is kite-linked.

What carries the argument

The H-linked property, which requires that any vertex mapping from the multigraph H extends to a subdivision of H inside G.

If this is right

  • k-connectivity suffices for F_k-linkage whenever F_k is connected.
  • 8-connectivity suffices for kite-linkage.
  • The exact connectivity threshold for kite-linkage lies in {7,8}.
  • The fat-triangle result provides a tool for proving linkage of other small multigraphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same method may yield connectivity bounds for linkage of other small graphs obtained by edge deletions from complete graphs.
  • Exact thresholds for other H could be settled by constructing counterexamples at connectivity one less than the bound.
  • These linkage results may interact with existing theorems on highly connected graphs containing subdivisions of fixed graphs.

Load-bearing premise

The results rest on the precise definitions of the k-fat-triangle as a three-vertex multigraph with k edges and the kite as K4 minus two edges at one vertex.

What would settle it

A single (k-1)-connected graph that is not F_k-linked for some connected F_k, or a single 7-connected graph that is not kite-linked.

Figures

Figures reproduced from arXiv: 1906.09197 by Gexin Yu, Martin Rolek, Runrun Liu.

Figure 1
Figure 1. Figure 1: A (u1, u2, u3, u4)-flower. Lemma 4.1. Suppose G is a 7-connected graph such that for some four vertices u2, u1, u3, u4 ∈ V (G), G contains no walk through u2, u1, u3, u2, u4 in order. Further suppose that there exist internally disjoint 7 [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Intermediate structure used to find a P4-linkage References [1] B. Bollob´as and A. Thomason. Highly linked graphs. Combinatorica, 16(3):313–320, 1996. [2] G. A. Dirac. In abstrakten Graphen vorhandene vollst¨andige 4-Graphen und ihre Unterteilungen. Math. Nachr., 22:61–85, 1960. [3] M. Ellingham, M. P. Plummer, and G. Yu. Diamond-linkage and P4-linkage. J. Graph Theory, 70(3):241–261, 2012. [4] R. J. Faud… view at source ↗
read the original abstract

For a multigraph $H$, a graph $G$ is $H$-linked if every injective mapping $\phi: V(H)\to V(G)$ can be extended to an $H$-subdivision in $G$. We study the minimum connectivity required for a graph to be $H$-linked. A $k$-fat-triangle $F_k$ is a multigraph with three vertices and a total of $k$ edges. We determine a sharp connectivity requirement for a graph to be $F_k$-linked. In particular, any $k$-connected graph is $F_k$-linked when $F_k$ is connected. A kite is the graph obtained from $K_4$ by removing two edges at a vertex. As a nontrivial application of $F_k$-linkage, we then prove that every $8$-connected graph is kite-linked, which shows that the required connectivity for a graph to be kite-linked is $7$ or $8$.

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 manuscript studies H-linkage for multigraphs H. It proves that any k-connected graph is F_k-linked whenever the multigraph F_k (three vertices, total of k edges) is connected. As a nontrivial application, it shows every 8-connected graph is kite-linked (kite obtained from K_4 by deleting two incident edges), implying the minimum connectivity guaranteeing kite-linkage lies between 7 and 8.

Significance. If the proofs hold, the results give sharp connectivity thresholds for a family of linkage problems and demonstrate a useful reduction from kite-linkage to fat-triangle linkage. The explicit connectivity bounds and the application to a concrete non-multigraph H advance the literature on subdivision and linkage properties in highly connected graphs.

minor comments (2)
  1. [Abstract] Abstract: the phrase 'removing two edges at a vertex' for the kite would be clearer if accompanied by a small diagram or explicit edge list in the introduction.
  2. [Introduction] The manuscript would benefit from an explicit statement of the lower-bound example showing that 7-connectivity is insufficient for kite-linkage (if such an example is present).

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript, the positive evaluation of its contributions, and the recommendation to accept.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper states two main theorems: any k-connected graph is F_k-linked (when F_k connected) and every 8-connected graph is kite-linked. These are presented as proved results using standard linkage definitions and connectivity arguments. No self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citations appear in the abstract or stated claims. The kite result is described as a nontrivial application of the fat-triangle result rather than an identity or renaming. The derivation chain relies on external graph-theoretic machinery without reducing to its own inputs by construction. This is the expected honest non-finding for a standard linkage paper.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper introduces no free parameters, new axioms beyond standard math, or invented entities; it works within established graph theory framework.

axioms (1)
  • standard math Standard definitions and properties of graphs, multigraphs, connectivity, and subdivisions.
    These are invoked throughout the definitions and results in the abstract.

pith-pipeline@v0.9.0 · 5692 in / 1065 out tokens · 71739 ms · 2026-05-25T18:48:51.463343+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

25 extracted references · 25 canonical work pages

  1. [1]

    Bollob´ as and A

    B. Bollob´ as and A. Thomason. Highly linked graphs. Combinatorica, 16(3):313–320, 1996

    work page 1996

  2. [2]

    G. A. Dirac. In abstrakten Graphen vorhandene vollst¨ an dige 4-Graphen und ihre Unterteilungen. Math. Nachr. , 22:61–85, 1960

    work page 1960

  3. [3]

    Ellingham, M

    M. Ellingham, M. P. Plummer, and G. Yu. Diamond-linkage a nd P4-linkage. J. Graph Theory , 70(3):241–261, 2012

    work page 2012

  4. [4]

    R. J. Faudree. Survery on results on k-ordered graphs. Discrete Math , 229:73–87, 2001

    work page 2001

  5. [5]

    Ferrara, R

    M. Ferrara, R. Gould, G. Tansey, and T. Whalen. On H-linked graphs. Graphs Combin. , 22(2):217–224, 2006

    work page 2006

  6. [6]

    R. J. Gould, A. V. Kostochka, and G. Yu. On minimum degree i mplying that a graph is H-linked. SIAM J. Discrete Math. , 20(4):829–840 (electronic), 2006

    work page 2006

  7. [7]

    H. A. Jung. Eine Verallgemeinerung des n-fachen Zusammenhangs f¨ ur Graphen.Math. Ann. , 187:95–103, 1970

    work page 1970

  8. [8]

    Kawarabayashi, A

    K. Kawarabayashi, A. V. Kostochka, and G. Yu. On sufficient degree conditions for a graph to be k-linked. Combin. Probab. Comput., 15(5):685–694, 2006

    work page 2006

  9. [9]

    A. V. Kostochka and G. Yu. An extremal problem for H-linked graphs. J. Graph Theory , 50(4):321–339, 2005

    work page 2005

  10. [10]

    A. V. Kostochka and G. Yu. Minimum degree conditions for H-linked graphs. Discrete Appl. Math. , 156(9):1542–1548, 2008

    work page 2008

  11. [11]

    A. V. Kostochka and G. Yu. Ore-type degree conditions fo r a graph to be H-linked. J. Graph Theory , 58(1):14–26, 2008

    work page 2008

  12. [12]

    D. G. Larman and P. Mani. On the existence of certain confi gurations within graphs and the 1-skeletons of polytopes. Proc. London Math. Soc. (3) , 20:144–160, 1970

    work page 1970

  13. [13]

    Q. Liu, D. B. W est, and G. Yu. Implications among linkage properties in graphs. J. Graph Theory , 60(4):327–337, 2009

    work page 2009

  14. [14]

    W. Mader. Homomorphieeigenschaften und mittlere Kant endichte von Graphen. Math. Ann. , 174:265–268, 1967

    work page 1967

  15. [15]

    W. Mader. ¨Uber die Maximalzahl kreuzungsfreier H-Wege. Arch. Math. (Basel) , 31:387–402, 1978

    work page 1978

  16. [16]

    McCarty, Y

    R. McCarty, Y. W ang, and X. Yu. 7-connected graphs are 4- ordered. https://arxiv.org/abs/1808.05124v2, 2018+

    work page arXiv 2018

  17. [17]

    Robertson, P

    N. Robertson, P. Seymour, and R. Thomas. Hadwiger’s con jecture for K6-free graphs. Combinatorica, 13(3):279–361, 1993

    work page 1993

  18. [18]

    Robertson and P

    N. Robertson and P. D. Seymour. Graph minors. XIII. The d isjoint paths problem. J. Combin. Theory Ser. B , 63(1):65–110, 1995

    work page 1995

  19. [19]

    Schrijver

    A. Schrijver. A short proof of Mader’s S-paths theorem. J. Combin. Theory, Ser. B , 82:319–321, 2001

    work page 2001

  20. [20]

    P. D. Seymour. Disjoint paths in graphs. Discrete Math. , 29(3):293–309, 1980

    work page 1980

  21. [21]

    Thomas and P

    R. Thomas and P. W ollan. An improved linear edge bound fo r graph linkages. European J. Combin. , 26(3-4):309–324, 2005

    work page 2005

  22. [22]

    Thomas and P

    R. Thomas and P. W ollan. The extremal function for 3-lin ked graphs. J. Combin. Theory Ser. B , 98(5):939–971, 2008

    work page 2008

  23. [23]

    Thomassen

    C. Thomassen. 2-linked graphs. European J. Combin. , 1(4):371–378, 1980

    work page 1980

  24. [24]

    M. E. W atkins and D. M. Mesner. Cycles and connectivity i n graphs. Canad. J. Math. , 19:1319–1328, 1967

    work page 1967

  25. [25]

    X. Yu. Disjoint paths in graphs. III. Characterization . Ann. Comb. , 7(2):229–246, 2003. 13

    work page 2003