Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 13 min ago
PreprintCC BY-NC-SA 4.0arXiv

A Four-Connected Graph without a Legal System

  • Qiuyu Chen
Open at sourcePDFDOICite

Abstract

In a 2021 paper, Jankiewicz, Norin, and Wise asked whether there exists a finite $4$-connected graph of girth at least four and nonnegative Charney--Davis curvature such that no $4$-connected ordinary subgraph admits a legal system. We construct such a graph by starting from the hexagonal prism and attaching three K3,4-based caps along pairwise disjoint induced $4$-cycles. The key structural input is a restriction theorem showing that a legal system on an induced-$4$-cycle amalgam restricts to each side, so the obstruction carried by the negatively curved prism survives the attachments. The resulting $33$-vertex graph is $4$-regular and $4$-connected, has girth four and Charney--Davis curvature one, and, by $4$-regularity, is its own unique $4$-connected ordinary subgraph.

Related

  1. Evolution of weights on a connected finite graph
    Jicheng Ma, Yunyan Yang
    Communications in Contemporary MathematicsPeer-reviewedLicence not statedFull text10 citedGeneral mathematicsOpenAlex
  2. On the sum of eccentric subgraph numbers of the vertices of a connected graph
    Akash De, Kamal Lochan Patra
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Research on graph theory segmentation method and dataset construction for connected handwritten digits
    Zhilai Zhang, Yang Zhang, Yang Wang
    PLOS OnePeer-reviewedCC BYFull textStatisticsPLOSEurope PMCPMC
  4. Every cubic graph has four total dominating sets covering each vertex at most twice
    Hyemin Kwon, Boram Park, Yoshio Sano
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Spectral extremal problems on 1-planar graphs without Friendship graph
    Jiamin Li, Dan Li, Yuanyuan Chen
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{chen2026fourconnected,
  title = {{A Four-Connected Graph without a Legal System}},
  author = {Qiuyu Chen},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.13419},
  eprint = {2609.13419},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.13419},
  note = {CC BY-NC-SA 4.0},
}
RIS
TY  - UNPB
TI  - A Four-Connected Graph without a Legal System
AU  - Qiuyu Chen
PY  - 2026
DA  - 2026/09/11
PB  - arXiv
DO  - 10.48550/arxiv.2609.13419
UR  - https://arxiv.org/abs/2609.13419
AB  - In a 2021 paper, Jankiewicz, Norin, and Wise asked whether there exists a finite $4$-connected graph of girth at least four and nonnegative Charney--Davis curvature such that no $4$-connected ordinary subgraph admits a legal system. We construct such a graph by starting from the hexagonal prism and attaching three K_3,4-based caps along pairwise disjoint induced $4$-cycles. The key structural input is a restriction theorem showing that a legal system on an induced-$4$-cycle amalgam restricts to each side, so the obstruction carried by the negatively curved prism survives the attachments. The resulting $33$-vertex graph is $4$-regular and $4$-connected, has girth four and Charney--Davis curvature one, and, by $4$-regularity, is its own unique $4$-connected ordinary subgraph.
ER  -