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.

Two-connected subgraphs stay in one incidence-forest piece

Statement

If the incidence graph of a finite hypergraph is a forest, every 2-connected subgraph of a graph realised on its hyperedges is contained, as an ordinary subgraph, in one hyperedge piece. Every single edge of the realisation lies in some hyperedge piece.

Facts & Assumptions

[F1]

For a finite hypergraph (V,E), the incidence graph has a vertex node for each member of V, a hyperedge node for each member of E, and an edge between them exactly when the vertex belongs to the hyperedge. In a realisation R, each piece Je has vertex set e, and the edge set of R is the union of the edge sets of the pieces. Berge cycles, incidence graphs and girth Graph realisations with possibly different hyperedge pieces

[F2]

A forest has no cycle. A path has distinct vertices; a cycle is a closed walk of length at least three with no repeated vertex except its endpoints. Every walk contains a path with the same endpoints. Connectedness means that every pair of vertices is joined by a path. Cycles, trees and forests in a simple graph on an arbitrary vertex set Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges Every walk between two vertices contains a path between the same endpoints Connected graphs and connected components defined by the existence of vertex paths

[F3]

A 2-connected graph has at least three vertices, is connected, and remains connected after deletion of any vertex. An ordinary subgraph has both its vertex set and edge set contained in those of the ambient graph. Cutvertices, 2-connected pieces and nontrivial blocks Subgraphs, induced subgraphs and spanning subgraphs

Proof

Given: A finite hypergraph whose incidence graph is a forest, a realisation R with pieces Je, and a 2-connected subgraph H of R.

Goal: Show that H is a subgraph of one piece and that every edge of R belongs to a piece.

1.1F1F2

Every edge of R belongs to a piece by the union defining R. Distinct hyperedges have at most one common vertex: two common vertices and the two hyperedge nodes would form a four-edge cycle in the incidence forest. In a forest there is at most one path between any two nodes: otherwise, after following two distinct paths from one endpoint to their first divergence and then to their first subsequent meeting, the two resulting internally disjoint path segments form a cycle.

2.1F1F2F3step 1.1

The connected graph H has an edge xy; choose a hyperedge e whose piece contains it. Suppose that H has a vertex z outside e. A path in H from x to z expands to an incidence walk by replacing each graph edge ab with a,f,b, where a piece indexed by f contains ab. Thus the node of z is connected to the node of e. Let P be their unique incidence path. Its first node after the node of e is a vertex node v with v∈e. At least one of x,y, say w, differs from v. The path from w to the node of e is the single incidence edge w,e, so uniqueness forces the path from w to z to pass through v. Consequently no incidence walk from w to z avoids v: such a walk would contain a path avoiding v, contrary to uniqueness.

3.1F1F2F3step 1.1step 2.1∎

Since H−v is connected and contains w and z, it has a w–z path. Expanding its edges into incidence walks as above gives a walk avoiding the vertex node v, a contradiction. Hence every vertex of H lies in e. Each edge ab of H belongs to some piece Jf; since a and b are distinct members of both e and f, step 1.1 gives f=e. Thus both the vertex and edge sets of H are contained in those of Je. The final assertion was established in step 1.1.

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.