Alphabeta Math
LemmaStatement: AI-generatedProof: AI-generated
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 q be a positive integer and let H=(V,E) be a finite hypergraph of Berge girth at least q. For any F⊆E with ∣F∣<q, the subgraph of the incidence graph induced by the hyperedge nodes belonging to F and all vertices incident with those hyperedges is a forest.

More precisely, for every integer s≥2, Berge cycles of length s using hyperedges in F correspond to incidence-graph cycles of length 2s in this induced subgraph, up to the choice of starting point and direction.

Facts & Assumptions

[F1]

In Berge cycles, incidence graphs and girth, the incidence graph has tagged vertex nodes (v,0) and hyperedge nodes (e,1), with an edge exactly when v∈e. A Berge cycle of length s≥2 has distinct hyperedges ei and distinct vertices xi satisfying xi∈ei∩ei+1 cyclically. Berge girth is the least such length, or infinity if there is no such cycle.

[F2]

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.

[F3]

The cardinality of a finite set counts its distinct members, as in The cardinality | A| of a finite set.

Proof

Given: A finite hypergraph H of Berge girth at least q and a family F of fewer than q hyperedges. Let IF be the induced subgraph specified in the statement.

Goal: Establish the cycle correspondence and prove that IF is a forest.

1.1F1F2construct

Let e0,…,es−1 and x0,…,xs−1 form a Berge cycle with all ei∈F. The alternating sequence (e0,1),(x0,0),(e1,1),(x1,0),…,(es−1,1),(xs−1,0),(e0,1) is a closed walk in IF: 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 2s. This includes s=2, where the four tagged nodes are distinct.

2.1F1F2step 1.1

Conversely, every edge of IF 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 2s with s≥2. Starting at a hyperedge node and choosing a direction gives the sequence in step 1.1; distinctness of the graph-cycle nodes makes the ei distinct and the xi distinct, while its edges give xi∈ei∩ei+1 cyclically. All ei lie in F, so these data form a Berge cycle of length s. The two constructions recover the same cyclic sequence, apart from starting point and direction.

3.1givenF1F2F3step 2.1∎

If IF had a cycle, step 2.1 would give a Berge cycle of length s with s distinct hyperedges in F. Hence s≤∣F∣<q, contradicting the assumed Berge girth. Thus IF has no cycle and is a forest; isolated selected vertices cannot create a cycle.

Depends on

Used by · 1

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.