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.
Connected subgraphs cannot cross anticomplete parts
Statement
Let be a finite simple graph whose vertex set is partitioned into parts such that no edge joins vertices in distinct parts. Every connected subgraph of has all its vertices in one part. In particular, the image of a connected graph under an ordinary or induced embedding into a disjoint graph family lies in one tagged part.
Facts & Assumptions
A finite simple graph has a finite vertex set and edges that are two-element subsets of it. A subgraph has a subset of the vertices and a subset of the edges of its ambient graph. A finite simple graph is a finite vertex set together with a set of two-element vertex subsets Subgraphs, induced subgraphs and spanning subgraphs
A connected graph is nonempty and every two of its vertices are joined by a path. A path is a finite list of distinct vertices whose consecutive pairs are edges; a one-vertex list is allowed. 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
The disjoint graph family has pairwise disjoint tagged parts covering its vertices, and no edge joins distinct tagged parts. Tagged graph families with anticomplete parts
An ordinary embedding is an injective vertex map preserving edges; its image vertices and image edges form a subgraph. An induced embedding is an ordinary embedding that also reflects edges. Ordinary embeddings as injections preserving edges Induced embeddings and induced copies of a graph
A set partition of a set is a family of nonempty, pairwise disjoint subsets whose union is that set. Thus each element belongs to exactly one block; the empty family partitions the empty set. Set partitions and blocks
Proof
Given: A graph with the stated partition and a connected subgraph of .
Goal: Show that lies in one part, and establish the embedding consequence.
Choose and let be the unique part containing . For any , connectivity gives a path in . Each consecutive pair is an edge of . Starting with , each successive vertex must also belong to : otherwise its edge from the preceding vertex would join distinct parts. Thus , including when . Consequently .
For an ordinary embedding of a connected graph into a disjoint graph family, take the subgraph formed by its image vertices and image edges. It is connected: the image of a path in is a path in that subgraph, since is injective and preserves edges. The nonempty tagged parts are pairwise disjoint and still cover the vertex set of the disjoint graph family, so they form a set partition; deleting empty parts changes neither coverage nor the no-crossing-edge property. The image is nonempty because is connected. Applying step 1.1 to this partition puts in one nonempty tagged part. An induced embedding is also an ordinary embedding, giving the same conclusion.
Depends on
- A finite simple graph is a finite vertex set together with a set of two-element vertex subsets
- Set partitions and blocks
- Subgraphs, induced subgraphs and spanning subgraphs
- 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
- Tagged graph families with anticomplete parts
- Ordinary embeddings as injections preserving edges
- Induced embeddings and induced copies of a graph
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.