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.
Statement references
Facts & Assumptions
For a finite hypergraph , the incidence graph has a vertex node for each member of , a hyperedge node for each member of , and an edge between them exactly when the vertex belongs to the hyperedge. In a realisation , each piece has vertex set , and the edge set of is the union of the edge sets of the pieces. Berge cycles, incidence graphs and girth Graph realisations with possibly different hyperedge pieces
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
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 with pieces , and a 2-connected subgraph of .
Goal: Show that is a subgraph of one piece and that every edge of belongs to a piece.
Every edge of belongs to a piece by the union defining . 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.
The connected graph has an edge ; choose a hyperedge whose piece contains it. Suppose that has a vertex outside . A path in from to expands to an incidence walk by replacing each graph edge with , where a piece indexed by contains . Thus the node of is connected to the node of . Let be their unique incidence path. Its first node after the node of is a vertex node with . At least one of , say , differs from . The path from to the node of is the single incidence edge , so uniqueness forces the path from to to pass through . Consequently no incidence walk from to avoids : such a walk would contain a path avoiding , contrary to uniqueness.
Since is connected and contains and , it has a – path. Expanding its edges into incidence walks as above gives a walk avoiding the vertex node , a contradiction. Hence every vertex of lies in . Each edge of belongs to some piece ; since and are distinct members of both and , step 1.1 gives . Thus both the vertex and edge sets of are contained in those of . The final assertion was established in step 1.1.
Depends on
- Graph realisations with possibly different hyperedge pieces
- Berge cycles, incidence graphs and girth
- Cutvertices, 2-connected pieces and nontrivial blocks
- Cycles, trees and forests in a simple graph on an arbitrary vertex set
- 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
- Subgraphs, induced subgraphs and spanning subgraphs
- Every walk between two vertices contains a path between the same endpoints
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.