Four connected graphs found without legal systems despite positive curvature
A Four-Connected Graph without a Legal System
Discrete Mathematics
Summary
The paper answers a complex question about a special type of network called a 4-connected graph. The authors show that there exists a particular network with certain properties—like having no small loops and a positive curvature measure—but still does not have a 'legal system,' a kind of substructure researchers study. They build this example starting from a known shape called a hexagonal prism and attach special parts to it. This construction proves that their example behaves uniquely in the way they asked about.
What this means in practice
- •For graph theorists: Clarify which 4-connected graphs can lack legal systems, guiding future graph classification efforts.
- •For network algorithm designers: Inform structural limitations of certain 4-connected networks relevant to design and analysis of communication schemes.
A theory result. No direct application yet.
Authors
Qiuyu Chen
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 $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.