LemmaStatement: AI-adaptedProof: 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.

Ordering targets and excluding H1 from H2

PDF p. 3: Section 3, paragraph beginning Assume without loss

Statement

Let $H_{1}, H_{2}$ be non-isomorphic connected finite simple graphs, each containing an edge. Label them so that $β (H_{1}) \geq β (H_{2})$ and, if equality holds, $∣ H_{1} ∣ \geq ∣ H_{2} ∣$ . Then $H_{2} \in Forb (H_{1})$ .

Here $∣ H ∣$ is the number of vertices of $H$ . A graph is connected if every two vertices are joined by a path. A block is a maximal 2-connected subgraph, or the subgraph consisting of a bridge and its endpoints; 2-connected means having at least three vertices, being connected, and remaining connected after any one vertex is deleted. A bridge is an edge whose deletion increases the number of connected components. Since each target has an edge, $β (H)$ is the largest number of vertices in a block of $H$ . Finally, $G \in Forb (H)$ means that $G$ contains no induced copy of $H$ : there is no injective vertex map preserving and reflecting adjacency between distinct vertices.

Statement references

Graph and colouring conventions

Blocks and the parameter beta

Order, size, complement and independence number

Induced forbidden-subgraph class

Induced embeddings and induced copies of a graph

Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges

Facts & Assumptions

[F1]

An induced embedding is an injective vertex map preserving and reflecting adjacency; in particular it is an ordinary embedding, an injective vertex map preserving edges. An induced copy exists exactly when such an embedding exists. Induced embeddings and induced copies of a graph Ordinary embeddings as injections preserving edges

[F2]

An ordinary embedding of one nonempty finite simple graph into another implies that the largest-block parameter of the first is at most that of the second. The parameter $b$ in that result equals $β$ under the block convention used here. Block containment and monotonicity under subgraphs Blocks and the parameter beta

[F3]

An injection between finite vertex sets is a bijection onto its image; the image has the cardinality of the domain and, as a subset of the target, has cardinality at most that of the target. 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

[F4]

An induced embedding between finite simple graphs of equal vertex order is an isomorphism. Rigidity of mutual ordinary embeddings

[F5]

Membership in $Forb (H)$ is precisely the absence of an induced copy of $H$ . Induced forbidden-subgraph class

Proof

Given: Non-isomorphic connected finite simple graphs $H_{1}, H_{2}$ , each with an edge, ordered as in the statement.

Goal: Show that $H_{2}$ contains no induced copy of $H_{1}$ .

1.1givenF1F2assume-contra

Suppose that $H_{2}$ contains an induced copy of $H_{1}$ . Its induced embedding is an ordinary embedding, so block monotonicity gives $β (H_{1}) \leq β (H_{2})$ . The given reverse inequality therefore forces equality. In particular, if the first inequality in the ordering were strict, the supposed copy would already be impossible.

2.1givenstep 1.1F1F3

In the equality case, the ordering gives $∣ H_{1} ∣ \geq ∣ H_{2} ∣$ . The induced embedding is injective, so finite cardinality gives $∣ H_{1} ∣ \leq ∣ H_{2} ∣$ . Hence the vertex orders are equal.

3.1givenstep 2.1F4F5discharge-contradiction∎

The induced embedding between these equal-order finite graphs is an isomorphism, contradicting the assumption that $H_{1}$ and $H_{2}$ are non-isomorphic. Thus no induced copy exists, and $H_{2} \in Forb (H_{1})$ by definition.

Depends on

Used by · 3

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.

Sources

Maria Axenovich and Patrick Schmitteckert, Non-isomorphic graphs have distinct vertex-Ramsey classes, arXiv:2610.03704v1 · PDF p. 3, Section 3, paragraph beginning Assume without loss