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.

Connected subgraphs cannot cross anticomplete parts

Statement

Let G 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 G 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

[F1]

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

[F2]

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

[F3]

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

[F4]

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

[F5]

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 G with the stated partition and a connected subgraph H of G.

Goal: Show that V(H) lies in one part, and establish the embedding consequence.

1.1givenF1F2F5

Choose u∈V(H) and let P be the unique part containing u. For any v∈V(H), connectivity gives a path u=v0,v1,…,vm=v in H. Each consecutive pair is an edge of G. Starting with v0∈P, each successive vertex must also belong to P: otherwise its edge from the preceding vertex would join distinct parts. Thus v∈P, including when m=0. Consequently V(H)⊆P.

2.1F2F3F4F5step 1.1∎

For an ordinary embedding f of a connected graph J 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 J is a path in that subgraph, since f 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 J is connected. Applying step 1.1 to this partition puts f(V(J)) in one nonempty tagged part. An induced embedding is also an ordinary embedding, giving the same conclusion.

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.