How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
Small edge supports in a high-girth hypergraph
Statement
Let be a positive integer and let be a finite hypergraph of Berge girth at least . For any with , the subgraph of the incidence graph induced by the hyperedge nodes belonging to and all vertices incident with those hyperedges is a forest.
More precisely, for every integer , Berge cycles of length using hyperedges in correspond to incidence-graph cycles of length in this induced subgraph, up to the choice of starting point and direction.
Statement references
Facts & Assumptions
In Berge cycles, incidence graphs and girth, the incidence graph has tagged vertex nodes and hyperedge nodes , with an edge exactly when . A Berge cycle of length has distinct hyperedges and distinct vertices satisfying cyclically. Berge girth is the least such length, or infinity if there is no such cycle.
By Cycles, trees and forests in a simple graph on an arbitrary vertex set, a cycle is a closed walk of length at least three with no repeated vertex except its endpoint, and a forest is a graph without cycles. An induced subgraph retains exactly the edges of the ambient graph between its selected vertices, as in Subgraphs, induced subgraphs and spanning subgraphs.
The cardinality of a finite set counts its distinct members, as in The cardinality | A| of a finite set.
Proof
Given: A finite hypergraph of Berge girth at least and a family of fewer than hyperedges. Let be the induced subgraph specified in the statement.
Goal: Establish the cycle correspondence and prove that is a forest.
Let and form a Berge cycle with all . The alternating sequence is a closed walk in : each consecutive pair is incident, and every displayed node belongs to the selected vertex set. The hyperedge nodes are distinct, the vertex nodes are distinct, and the tags separate the two kinds. Thus it is a graph cycle of length . This includes , where the four tagged nodes are distinct.
Conversely, every edge of joins a vertex node to a hyperedge node. A cycle in it therefore alternates between the two kinds. Its length is even and at least four, say with . Starting at a hyperedge node and choosing a direction gives the sequence in step 1.1; distinctness of the graph-cycle nodes makes the distinct and the distinct, while its edges give cyclically. All lie in , so these data form a Berge cycle of length . The two constructions recover the same cyclic sequence, apart from starting point and direction.
If had a cycle, step 2.1 would give a Berge cycle of length with distinct hyperedges in . Hence , contradicting the assumed Berge girth. Thus has no cycle and is a forest; isolated selected vertices cannot create a cycle.
Depends on
Dependency tree · 2 levels
Each result is drawn at its shortest distance from this item. Arrows run from prerequisites to the items that use them; this item has a heavier outline. External source nodes link directly to the cited text. The view shows up to two dependency steps; open a prerequisite to continue.