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 be a graph realisation over a finite hypergraph of Berge girth at least an integer . If a 2-connected graph with edges and occurs as an ordinary subgraph of , then that occurrence is contained in one hyperedge piece. Every occurrence of is likewise contained in a piece. Consequently, if every piece excludes as an ordinary subgraph, then so does , whenever is 2-connected with fewer than edges or .
Here an occurrence of a graph in a graph means an ordinary subgraph of that is isomorphic to . Excluding 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
A finite hypergraph is a finite vertex set with a set of subsets called hyperedges. Its realisation has vertex set and edge set , where the piece has vertex set . 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
A 2-connected graph has at least three vertices, is connected, and remains connected after deletion of any one vertex. is the graph consisting of two vertices and their single edge. Cutvertices, 2-connected pieces and nontrivial blocks Subgraphs, induced subgraphs and spanning subgraphs
Berge girth is the least length of a Berge cycle, or infinity if no such cycle exists. For fewer than selected hyperedges of a finite hypergraph of Berge girth at least , 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
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
A graph isomorphism is a bijection of vertex sets preserving and reflecting adjacency between distinct vertices. Graph isomorphisms, automorphisms and graph complements
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
A finite set of cardinality admits a listing without repetition , and a bijection transports finiteness and cardinality. A subset of a finite set is finite and has no larger cardinality. Every nonempty subset of 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 of a finite hypergraph of Berge girth at least , and an occurrence in of a 2-connected graph having edges.
Goal: Place in one piece, establish the corresponding assertion for , and deduce the exclusion statement.
By the occurrence convention, choose an isomorphism . The map is a bijection from to : adjacency preservation makes it well-defined, injectivity of makes it injective on unordered pairs, and adjacency reflection and surjectivity of make it surjective. Thus has edges, and the vertex bijection gives it at least three vertices. Applying to a path preserves distinctness of its vertices and adjacency of consecutive vertices. Paths in the connected graph therefore show that is connected. For any vertex of , paths between any two other preimages in after deletion of map to paths between the corresponding vertices of avoiding . Thus remains connected after deletion of any one vertex, so is 2-connected.
For each of the finitely many edges of , choose one hyperedge whose piece supplies that edge; such a hyperedge exists by the union defining . Denote the chosen hyperedge for an edge by , and let . Choose a listing without repetition of , which exists by its cardinality .
For each , the set of indices with and is a nonempty subset of . Let be its least element, supplied by F7, and set . The map is surjective onto by its definition. It is injective because implies . Thus its inverse, which sends to , is a bijection from to . The finite-subset bound makes finite with . Cardinality transport along this bijection makes finite with .
Form the restricted hypergraph and realise it using the same pieces indexed by . Its realisation has vertex set and contains every edge of by the choice of , so is its ordinary subgraph.
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 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 inside one selected piece. That piece is also a piece of .
An occurrence of consists of one edge and its endpoints, since its isomorphism with 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 is as in the final assertion and an occurrence existed in , step 5.1 or this argument would put it in a piece, contrary to the assumed exclusion.
Depends on
- Graph realisations with possibly different hyperedge pieces
- Berge cycles, incidence graphs and girth
- Small edge supports in a high-girth hypergraph
- Two-connected subgraphs stay in one incidence-forest piece
- Cutvertices, 2-connected pieces and nontrivial blocks
- The cardinality | A| of a finite set
- Subgraphs, induced subgraphs and spanning subgraphs
- Cycles, trees and forests in a simple graph on an arbitrary vertex set
- Graph isomorphisms, automorphisms and graph complements
- Connected graphs and connected components defined by the existence of vertex paths
- Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges
- 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
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.