pith. sign in

arxiv: 2605.06378 · v1 · submitted 2026-05-07 · 🧮 math.CO

The maximum number of k-cliques of 7-connected 1-planar graphs

Yuanqiu Huang , Licheng Zhang This is my paper

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

classification 🧮 math.CO
keywords 1-planar graphs7-connected graphsclique enumerationextremal graph theorytriangle countingK4 counting
0
0 comments X

The pith

Every n-vertex 7-connected 1-planar graph has at most 4n-12 edges, 4n-16 triangles, and n-6 copies of K4.

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

The paper proves upper bounds on edges, triangles, and K4 subgraphs specifically for 7-connected 1-planar graphs. These limits are stricter than those for 1-planar graphs of lower connectivity because the higher minimum degree and vertex connectivity restrict how the graph can be drawn and how many small complete subgraphs it can contain. The resulting total clique count is at most 10n-33. The bounds are achieved by explicit constructions that work for infinitely many values of n.

Core claim

We prove that every n-vertex 7-connected 1-planar graph has at most 4n-12 edges, 4n-16 triangles, and n-6 copies of K4. Hence the total number of cliques is at most 10n-33. All bounds are sharp for infinitely many values of n.

What carries the argument

7-connectivity together with 1-planarity, which restricts the possible density and forces the use of structural counting arguments to bound edges and small cliques.

If this is right

  • The maximum number of edges is 4n-12.
  • The maximum number of triangles is 4n-16.
  • The maximum number of K4 copies is n-6.
  • The total number of cliques of any size is therefore at most 10n-33.

Where Pith is reading between the lines

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

  • The same connectivity threshold may produce linear bounds on larger cliques as well.
  • These graphs must be sparser than typical 1-planar graphs and closer in density to planar graphs.
  • The extremal constructions likely consist of stacked or triangulated near-planar blocks that remain 7-connected.

Load-bearing premise

The graphs are required to satisfy both 7-connectivity and 1-planarity simultaneously.

What would settle it

A single 7-connected 1-planar graph on n vertices that contains more than 4n-12 edges, more than 4n-16 triangles, or more than n-6 copies of K4.

Figures

Figures reproduced from arXiv: 2605.06378 by Licheng Zhang, Yuanqiu Huang.

Figure 1
Figure 1. Figure 1: The two weakly inequivalent 1-planar drawings of 𝐾4: (a) tetrahedral and (b) pyramidal; and (c) the unique 1-planar drawing of 𝐾5. Lemma 6 (Gollin et al. [5]). Let 𝐺 be a 3-connected maximal 1-planar graph of order at least five. Then 𝐺 has a rich 1-planar drawing 𝜙 such that 𝐻 = S (𝜙) is 3-connected and every face of 𝐻 has degree three or four. Moreover, N (𝐺, 𝐾3) = 𝑠3 (𝐻) + 𝑓3(𝐻) + 4 𝑓4(𝐻). 3. The planar… view at source ↗
read the original abstract

In 2023, Gollin, Hendrey, Methuku, Tompkins and Zhang determined the maximum number of cliques in general 1-planar graphs with order $n$. Their extremal examples have connectivity at most three, except for a few small orders. At the high-connectivity end, we prove that every $n$-vertex 7-connected 1-planar graph has at most $4n-12$ edges, $4n-16$ triangles, and $n-6$ copies of $K_4$. Hence the total number of cliques is at most $10n-33$. All bounds are sharp for infinitely many values of $n$.

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

1 major / 0 minor

Summary. The manuscript claims that every n-vertex 7-connected 1-planar graph has at most 4n-12 edges, 4n-16 triangles, and n-6 copies of K_4. It concludes that the total number of cliques is therefore at most 10n-33, with all bounds sharp for infinitely many n. This refines earlier extremal results on cliques in 1-planar graphs by restricting to the 7-connected case.

Significance. If the individual bounds hold, the paper supplies explicit linear upper bounds on small-clique counts together with matching infinite families of extremal examples. These results clarify the additional restrictions imposed by 7-connectivity on 1-planar graphs and provide concrete, falsifiable statements that can be checked against known constructions or used in further structural theory.

major comments (1)
  1. [Abstract] Abstract: the claimed total of 10n-33 cliques does not follow from the three stated bounds. Adding the n copies of K_1 to the given quantities for K_2, K_3 and K_4 produces n + (4n-12) + (4n-16) + (n-6) = 10n-34. This arithmetic discrepancy directly affects the central 'hence' statement and must be corrected or clarified.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for identifying the arithmetic discrepancy in the abstract. We address the comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the claimed total of 10n-33 cliques does not follow from the three stated bounds. Adding the n copies of K_1 to the given quantities for K_2, K_3 and K_4 produces n + (4n-12) + (4n-16) + (n-6) = 10n-34. This arithmetic discrepancy directly affects the central 'hence' statement and must be corrected or clarified.

    Authors: We agree with the referee that the sum of the stated upper bounds is exactly 10n-34. The manuscript contains an arithmetic error in the abstract when claiming that the total number of cliques is at most 10n-33. Since the number of cliques is the sum of the numbers of K_1, K_2, K_3 and K_4, and each is bounded above by the quantities given, the correct immediate consequence is an upper bound of 10n-34. We will revise the abstract (and any corresponding statement in the introduction) to read 'at most 10n-34'. The individual bounds on edges, triangles and K_4 remain as proved in the body of the paper, and the extremal constructions continue to show that each of those three bounds is tight for infinitely many n. The referee's observation does not affect the validity of the proofs for the separate bounds. revision: yes

Circularity Check

0 steps flagged

No significant circularity; bounds are direct combinatorial results

full rationale

The paper states explicit upper bounds on edges (K2), triangles (K3), and K4 copies in 7-connected 1-planar graphs, then adds them (with an off-by-one arithmetic slip in the total) to obtain the clique count bound. This summation is a straightforward consequence of the individual bounds and does not reduce any quantity to itself by definition or by a fitted parameter. No self-citation is invoked as a load-bearing uniqueness theorem or ansatz; the 2023 reference provides only background context for the low-connectivity case. The derivation chain relies on structural properties of the joint 7-connectivity + 1-planarity assumptions and is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard axioms of graph theory and known structural facts about 1-planar graphs; no free parameters, new entities, or ad-hoc assumptions are introduced in the abstract.

axioms (1)
  • standard math Standard definitions and basic properties of 1-planar graphs and vertex-connectivity
    Invoked throughout the statement of the main theorem.

pith-pipeline@v0.9.0 · 5410 in / 1129 out tokens · 26790 ms · 2026-05-08T08:07:13.011909+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

13 extracted references · 13 canonical work pages

  1. [1]

    Alon and Y

    N. Alon and Y. Caro, On the number of subgraphs of prescribed type of planar graphs with a given number of vertices,Annals of Discrete Mathematics20(1984), 25–36

    work page 1984

  2. [2]

    T.Biedl,Anoteon1-planargraphswithminimumdegree7,DiscreteAppl.Math.289(2021), 230–232

    work page 2021

  3. [3]

    Bodendiek, H

    R. Bodendiek, H. Schumacher and K. Wagner, Bemerkungen zu einem Sechsfarbenproblem von G. Ringel,Abh. Math. Sem. Univ. Hamburg53(1983), 41–52

    work page 1983

  4. [4]

    Fabrici and T

    I. Fabrici and T. Madaras, The structure of 1-planar graphs,Discrete Math.307(2007), 854–865

    work page 2007

  5. [5]

    Combin.109(2023), 103654

    J.P.Gollin,K.Hendrey,A.Methuku,C.TompkinsandX.Zhang,Countingcliquesin1-planar graphs,European J. Combin.109(2023), 103654

    work page 2023

  6. [6]

    Hakimi and E.F

    S.L. Hakimi and E.F. Schmeichel, On the number of cycles of length𝑘in a maximal planar graph,J. Graph Theory3(1979), 69–86

    work page 1979

  7. [7]

    Hoffmann, M.M

    M. Hoffmann, M.M. Reddy and E. Seemann, Hamiltonian cycles and matchings in 1-planar graphs, inAbstracts of the 39th European Workshop on Computational Geometry (EuroCG 2023), Barcelona, Spain, 2023, 34:1–34:7

    work page 2023

  8. [8]

    Y.Huang,L.ZhangandY.Wang,Thematchingextendabilityof7-connectedmaximal1-plane graphs,Discuss. Math. Graph Theory44(2024), 777–790

    work page 2024

  9. [9]

    Matsumoto and Y

    N. Matsumoto and Y. Suzuki, Non-1-planarity of lexicographic products of graphs,Discuss. Math. Graph Theory41(2021), 1103–1114

    work page 2021

  10. [10]

    Ringel, Ein Sechsfarbenproblem auf der Kugel,Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg29 (1965), 107–117

    G. Ringel, Ein Sechsfarbenproblem auf der Kugel,Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg29 (1965), 107–117

    work page 1965

  11. [11]

    Tutte, How to draw a graph,Proc

    W.T. Tutte, How to draw a graph,Proc. London Math. Soc.13(1963), 743–767. THE MAXIMUM NUMBER OF𝑘-CLIQUES OF 7-CONNECTED 1-PLANAR GRAPHS 7

    work page 1963

  12. [12]

    Wood, On the maximum number of cliques in a graph,Graphs Combin.23(2007), 337–352

    D.R. Wood, On the maximum number of cliques in a graph,Graphs Combin.23(2007), 337–352

    work page 2007

  13. [13]

    School of Mathematics and Statistics, Hunan Normal University , Changsha, Hunan 410081, P .R

    A.A.Zykov,Onsomepropertiesoflinearcomplexes,inRussian,Mat.SbornikN.S.24(1949), 163–188. School of Mathematics and Statistics, Hunan Normal University , Changsha, Hunan 410081, P .R. China Email address:hyqq@hunnu.edu.cn School of Mathematics and Statistics, Hunan Normal University , Changsha, Hunan 410081, P .R. China Email address:lczhangmath@163.com

    work page 1949