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 2-connected subgraphs localise in high-girth pieces

Statement

Let R be a graph realisation over a finite hypergraph of Berge girth at least an integer q≥3. If a 2-connected graph B with m edges and m<q occurs as an ordinary subgraph of R, then that occurrence is contained in one hyperedge piece. Every occurrence of K2 is likewise contained in a piece. Consequently, if every piece excludes B as an ordinary subgraph, then so does R, whenever B is 2-connected with fewer than q edges or B=K2.

Here an occurrence of a graph B in a graph X means an ordinary subgraph H of X that is isomorphic to B. Excluding B means having no such occurrence. Containment of an occurrence in a piece means containment of both its vertex set and its edge set in that piece.

Facts & Assumptions

[F1]

A finite hypergraph is a finite vertex set V with a set E of subsets called hyperedges. Its realisation has vertex set V and edge set ⋃e∈EE(Je), where the piece Je has vertex set e. An ordinary subgraph has vertex and edge sets contained in those of its ambient graph. Graph realisations with possibly different hyperedge pieces Subgraphs, induced subgraphs and spanning subgraphs

[F2]

A 2-connected graph has at least three vertices, is connected, and remains connected after deletion of any one vertex. K2 is the graph consisting of two vertices and their single edge. Cutvertices, 2-connected pieces and nontrivial blocks Subgraphs, induced subgraphs and spanning subgraphs

[F3]

Berge girth is the least length of a Berge cycle, or infinity if no such cycle exists. For fewer than q selected hyperedges of a finite hypergraph of Berge girth at least q, the incidence graph induced by their hyperedge nodes and their incident vertex nodes is a forest. A forest is a graph without cycles. Berge cycles, incidence graphs and girth Small edge supports in a high-girth hypergraph Cycles, trees and forests in a simple graph on an arbitrary vertex set

[F4]

In a realisation of a finite hypergraph whose incidence graph is a forest, every 2-connected subgraph is contained in one piece. Finite cardinality counts distinct members of a finite set. Two-connected subgraphs stay in one incidence-forest piece The cardinality | A| of a finite set

[F5]

A graph isomorphism f:B→H is a bijection of vertex sets preserving and reflecting adjacency between distinct vertices. Graph isomorphisms, automorphisms and graph complements

[F6]

A path is a finite vertex list with distinct vertices and adjacent consecutive vertices. A graph is connected when its vertex set is nonempty and every two vertices are joined by a path. Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges Connected graphs and connected components defined by the existence of vertex paths

[F7]

A finite set of cardinality m admits a listing without repetition a0,…,am−1, and a bijection transports finiteness and cardinality. A subset of a finite set is finite and has no larger cardinality. Every nonempty subset of N has a least element. A map is injective when equal images force equal arguments, surjective when every member of its codomain is an image, and bijective when both conditions hold. The cardinality | A| of a finite set A subset of a finite set is finite, with | B| ≤ | A|, and equality holds if and only if B = A The well-ordering principle Injection, surjection, bijection

Proof

Given: A realisation R of a finite hypergraph of Berge girth at least q≥3, and an occurrence H in R of a 2-connected graph B having m<q edges.

Goal: Place H in one piece, establish the corresponding assertion for K2, and deduce the exclusion statement.

1.1givenF2F4F5F6choose

By the occurrence convention, choose an isomorphism f:B→H. The map {u,v}↦{f(u),f(v)} is a bijection from E(B) to E(H): adjacency preservation makes it well-defined, injectivity of f makes it injective on unordered pairs, and adjacency reflection and surjectivity of f make it surjective. Thus H has m edges, and the vertex bijection gives it at least three vertices. Applying f to a path preserves distinctness of its vertices and adjacency of consecutive vertices. Paths in the connected graph B therefore show that H is connected. For any vertex h=f(v) of H, paths between any two other preimages in B after deletion of v map to paths between the corresponding vertices of H avoiding h. Thus H remains connected after deletion of any one vertex, so H is 2-connected.

2.1F1F7step 1.1choose

For each of the finitely many edges of H, choose one hyperedge whose piece supplies that edge; such a hyperedge exists by the union defining R. Denote the chosen hyperedge for an edge a by c(a), and let F={c(a):a∈E(H)}. Choose a listing without repetition a0,…,am−1 of E(H), which exists by its cardinality m.

3.1givenF7step 1.1step 2.1construct

For each e∈F, the set of indices i with 0≤i<m and c(ai)=e is a nonempty subset of N. Let i(e) be its least element, supplied by F7, and set D={ai(e):e∈F}⊆E(H). The map e↦ai(e) is surjective onto D by its definition. It is injective because ai(e)=ai(e′) implies e=c(ai(e))=c(ai(e′))=e′. Thus its inverse, which sends a∈D to c(a), is a bijection from D to F. The finite-subset bound makes D finite with ∣D∣≤∣E(H)∣=m. Cardinality transport along this bijection makes F finite with ∣F∣=∣D∣≤m<q.

4.1F1step 2.1step 3.1construct

Form the restricted hypergraph (V,F) and realise it using the same pieces indexed by F. Its realisation has vertex set V and contains every edge of H by the choice of c, so H is its ordinary subgraph.

5.1givenF1F3F4step 1.1step 3.1step 4.1

By the support-forest result, the incidence graph on the selected hyperedge nodes and their incident vertex nodes is a forest. The incidence graph of (V,F) adds only isolated vertex nodes, which cannot belong to a cycle, and is therefore also a forest. The forest-realisation result now puts the 2-connected subgraph H inside one selected piece. That piece is also a piece of R.

6.1F1F2F5step 5.1∎

An occurrence of K2 consists of one edge and its endpoints, since its isomorphism with K2 is a vertex bijection preserving and reflecting adjacency. The edge belongs to some piece by the defining union, and that piece contains its endpoints; hence the occurrence is contained in that piece. If B is as in the final assertion and an occurrence existed in R, step 5.1 or this argument would put it in a piece, contrary to the assumed exclusion.

Depends on

Used by · 2

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.