pith. sign in

arxiv: 2606.22106 · v1 · pith:SVTFQG33new · submitted 2026-06-20 · 🧮 math.CO

Rainbow triangles in edge-colored graphs with large minimum color degree

Bo Ning , Yuting Tian This is my paper

Pith reviewed 2026-06-26 11:46 UTC · model grok-4.3

classification 🧮 math.CO
keywords rainbow trianglesedge-colored graphsminimum color degreeextremal functiongraph theorycombinatorics
0
0 comments X

The pith

The minimum number of rainbow triangles in any n-vertex edge-colored graph with minimum color degree at least (n+1)/2 equals (n²-1)/8 for odd n≥3, n²/4−1 for even n≥6, and 4 for n=4.

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

This paper determines the exact value of f(n), the smallest possible number of rainbow triangles in an n-vertex edge-colored graph whose minimum color degree is at least (n+1)/2. Earlier results established only that at least one rainbow triangle must exist under this degree condition. The authors construct families of graphs that meet the color-degree requirement and contain precisely the stated number of rainbow triangles, then prove that every graph satisfying the condition has at least this many.

Core claim

f(n) equals (n²-1)/8 when n is odd and at least 3, equals n²/4−1 when n is even and at least 6, and equals 4 when n=4. These values are obtained by exhibiting explicit edge-colored graphs that attain them while obeying the minimum color-degree bound, together with a proof that no such graph can have fewer rainbow triangles.

What carries the argument

The extremal function f(n) defined as the minimum of rt(G) over all n-vertex edge-colored graphs G with δc(G)≥(n+1)/2, together with the specific constructions that achieve the bound.

If this is right

  • Every qualifying graph on odd n has at least (n²-1)/8 rainbow triangles.
  • Every qualifying graph on even n≥6 has at least n²/4−1 rainbow triangles.
  • The n=4 case is settled at exactly 4 rainbow triangles.
  • The function f(n) is now known for every n.

Where Pith is reading between the lines

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

  • The same constructions may supply test cases for counting rainbow copies of K4 or C4 under the same color-degree hypothesis.
  • The exact minimum could be used to calibrate the expected number of rainbow triangles in random colorings that obey the degree lower bound.
  • Analogous exact minima may exist for rainbow copies of other fixed subgraphs when the color degree is slightly above n/2.

Load-bearing premise

The listed constructions are the only graphs that could possibly attain fewer rainbow triangles while still satisfying the minimum color-degree condition.

What would settle it

An n-vertex edge-colored graph with minimum color degree at least (n+1)/2 but strictly fewer than the stated f(n) rainbow triangles.

read the original abstract

Let $G$ be an edge-colored graph on $n$ vertices, and let $\deltac(G)$ denote its minimum color degree. Li and, independently Li, Ning, Xu, and Zhang, proved that every edge-colored graph on $n$ vertices with $\deltac(G) \ge \frac{n+1}{2}$ contains a rainbow triangle. Let $\rt(G)$ denote the number of rainbow triangles in $G$, and define \[ f(n) = \min\{ \rt(G) : |V(G)| = n,\ \deltac(G) \ge (n+1)/2 \}. \] In \cite{LiNingShiZhang2024}, the following open problem was posed: determine all the values of $f(n)$. In this paper, we determine $f(n)$ completely: $f(n) = (n^2-1)/8$ for odd $n\geq 3$, $f(n) = \frac{n^2}{4} - 1$ for all even $n \ge 6,$ and $f(4) = 4$. This resolves an open problem raised in \cite{LiNingShiZhang2024}.

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 determines the exact minimum f(n) of rainbow triangles over all n-vertex edge-colored graphs G satisfying δ_c(G) ≥ (n+1)/2. It asserts that this minimum equals (n²-1)/8 for odd n≥3, equals n²/4−1 for even n≥6, and equals 4 when n=4, via explicit constructions attaining the bound together with a proof that no other graph meeting the color-degree hypothesis has fewer rainbow triangles. This resolves the open problem posed in LiNingShiZhang2024.

Significance. The result supplies the precise extremal function for the number of rainbow triangles under the color-degree threshold already known to guarantee at least one such triangle. The explicit constructions that meet the degree condition and the claim that they are minimal constitute the main contribution; if the structural argument establishing minimality is correct, the paper gives a complete quantitative strengthening of the earlier existence theorem.

minor comments (2)
  1. Abstract: the even-case formula is written once in inline math and once in text; ensure identical rendering throughout the manuscript.
  2. The citation LiNingShiZhang2024 appears in the abstract; confirm that the corresponding bibliography entry is complete and that the earlier existence theorem is cited at the appropriate place in the introduction.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive report and recommendation to accept the manuscript. The summary accurately describes our determination of the extremal function f(n).

Circularity Check

0 steps flagged

No significant circularity; result rests on independent existence theorem and explicit constructions

full rationale

The paper defines f(n) explicitly as the minimum rt(G) over graphs meeting the δ_c(G) ≥ (n+1)/2 condition. It cites prior work (including overlapping authors) only for the existence of at least one rainbow triangle and for posing the open problem of determining the exact minimum. No equation, definition, or self-citation reduces the claimed closed-form values of f(n) to a fitted parameter or to the input by construction. The structural claim that the exhibited graphs are extremal is asserted as the content of the new proof and is not shown to collapse into a renaming or self-referential fit. This is the normal case of a paper solving its own open problem without circular reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result is an exact combinatorial determination; it introduces no new entities, no fitted numerical parameters, and relies only on the standard axioms of graph theory and edge colorings.

axioms (1)
  • standard math Basic definitions and axioms of graphs, edges, and proper or improper edge colorings
    The entire development rests on the usual language of edge-colored graphs.

pith-pipeline@v0.9.1-grok · 5739 in / 1238 out tokens · 32195 ms · 2026-06-26T11:46:09.778174+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

23 extracted references

  1. [1]

    Aharoni, E

    R. Aharoni, E. Berger, M. Chudnovsky, H. Guo, and S. Zerbib, Nonuni- form degrees and rainbow versions of the Caccetta–H¨ aggkvist conjec- ture,SIAM J. Discrete Math.37(2023), 1704–1714

    2023

  2. [2]

    Aharoni, M

    R. Aharoni, M. DeVos, S. G. H. de la Maza, A. Montejano, and R.ˇS´ amal, A rainbow version of Mantel’s theorem,Adv. Comb.(2020), Paper No. 2, 12 pp

    2020

  3. [3]

    Aharoni, M

    R. Aharoni, M. DeVos, and R. Holzman, Rainbow triangles and the Caccetta–H¨ aggkvist conjecture,J. Graph Theory92(2019), 347–360

    2019

  4. [4]

    Balogh, P

    J. Balogh, P. Hu, B. Lidick´ y, F. Pfender, J. Volec, and M. Young, Rain- bow triangles in three-colored graphs,J. Combin. Theory Ser. B126 (2017), 83–113

    2017

  5. [5]

    ˇCada, A

    R. ˇCada, A. Kaneko, Z. Ryj´ aˇ cek and K. Yoshimoto, Rainbow cycles in edge-colored graphs,Discrete Math.339(2016), no. 4, 1387–1392

    2016

  6. [6]

    Chase, The maximum number of triangles in a graph of given maxi- mum degree,Adv

    Z. Chase, The maximum number of triangles in a graph of given maxi- mum degree,Adv. Comb.(2020), Paper No. 10, 5 pp

    2020

  7. [7]

    Czygrinow, T

    A. Czygrinow, T. Molla, B. Nagle and R. Oursler, On odd rainbow cycles in edge-colored graphs,European J. Combin.94(2021), Paper No. 103316, 10 pp

    2021

  8. [8]

    Ehard and E

    S. Ehard and E. Mohr, Rainbow triangles and cliques in edge-colored graphs,European J. Combin.84(2020), Paper No. 103037, 12 pp

    2020

  9. [9]

    Erd˝ os, On a theorem of Rademacher–Tur´ an,Illinois J

    P. Erd˝ os, On a theorem of Rademacher–Tur´ an,Illinois J. Math.6 (1962), 122–127

    1962

  10. [10]

    Erd˝ os, On the number of complete subgraphs contained in certain graphs,Magy

    P. Erd˝ os, On the number of complete subgraphs contained in certain graphs,Magy. Tud. Akad. Mat. Kut. Int. Kozl.,7(1962), 459–464

    1962

  11. [11]

    D. C. Fisher, Lower bounds on the number of triangles in a graph,J. Graph Theory13(1989), 505–512. 14

    1989

  12. [12]

    Fujita, B

    S. Fujita, B. Ning, C. Xu, and S. Zhang, On sufficient conditions for rainbow cycles in edge-colored graphs,Discrete Math.342(2019), 1956– 1965

    2019

  13. [13]

    Gan, P.-S

    W. Gan, P.-S. Loh, and B. Sudakov, Maximizing the number of indepen- dent sets of a fixed size,Combin. Probab. Comput.24(2015), 521–527

    2015

  14. [14]

    A. W. Goodman, On sets of acquaintances and strangers at any party, Amer. Math. Monthly66(1959), 778–783

    1959

  15. [15]

    Z. He, P. Frankl, E. Gy˝ ori, Z. Lv, N. Salia, C. Tompkins, K. Varga and X. Zhu, Extremal results for graphs avoiding a rainbow subgraph, Electron. J. Combin.31(2024), no. 1, Paper No. P1.28, 11 pp

    2024

  16. [16]

    Kano and X

    M. Kano and X. Li, Monochromatic and heterochromatic subgraphs in edge-colored graphs: a survey,Graphs Combin.24(2008), 237–263

    2008

  17. [17]

    B. Li, B. Ning, C. Xu, and S. Zhang, Rainbow triangles in edge-colored graphs,European J. Combin.36(2014), 453–459

    2014

  18. [18]

    Li and G

    H. Li and G. Wang, Color degree and heterochromatic cycles in edge- colored graphs,European J. Combin.33(2012), 1958–1964

    2012

  19. [19]

    Li, RainbowC 3’s andC 4’s in edge-colored graphs,Discrete Math

    H. Li, RainbowC 3’s andC 4’s in edge-colored graphs,Discrete Math. 313(2013), 1893–1896

    2013

  20. [20]

    R. Li, B. Ning, and S. Zhang, Color degree sum conditions for rainbow triangles in edge-colored graphs,Graphs Combin.32(2016), 2001–2008

    2016

  21. [21]

    X. Li, B. Ning, Y. Shi, and S. Zhang, Counting rainbow triangles in edge-colored graphs,J. Graph Theory107(2024), 742–758

    2024

  22. [22]

    Lo, Cliques in graphs with bounded minimum degree,Combin

    A. Lo, Cliques in graphs with bounded minimum degree,Combin. Probab. Comput.21(2012), 457–482

    2012

  23. [23]

    Lov´ asz and M

    L. Lov´ asz and M. Simonovits, On the number of complete subgraphs of a graph II, inStudies in Pure Mathematics, Akad´ emiai Kiad´ o, Budapest and Birkh¨ auser, Basel, (1983), 459–495. 15

    1983