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.

Orienting equal-order non-isomorphic targets

PDF p. 2: Section 3, ordinary classes, equal-order case

Statement

Let $H_{1}$ and $H_{2}$ be non-isomorphic finite simple graphs of the same order, each with at least one vertex. Their labels can be chosen so that $H_{2}$ contains no copy of $H_{1}$ .

The order of a graph is the number of its vertices. A copy of $H_{1}$ in $H_{2}$ is a subgraph of $H_{2}$ isomorphic to $H_{1}$ ; it need not be induced. A graph isomorphism is a bijection of vertex sets preserving and reflecting adjacency.

Facts & Assumptions

[F1]

A copy of a finite simple graph $J$ in a finite simple graph $L$ exists exactly when an ordinary embedding $J \to L$ exists. An ordinary embedding is an injective vertex map that preserves edges (Ordinary embeddings as injections preserving edges).

[F2]

If two finite simple graphs admit ordinary embeddings in both directions, then they are isomorphic (Rigidity of mutual ordinary embeddings).

[F3]

The order of a finite graph is the cardinality of its vertex set (Order, size, complement and independence number).

Proof

Given: Non-isomorphic finite simple graphs $H_{1}, H_{2}$ of equal order, each with at least one vertex.

Goal: Choose their labels so that $H_{2}$ has no copy of $H_{1}$ .

1.1givenF2

Ordinary embeddings cannot exist in both directions between the two graphs, since otherwise the rigidity fact would make them isomorphic, contrary to the hypothesis. Hence at least one direction has no ordinary embedding.

2.1givenF1F3step 1.1∎

Label the source of a direction without an ordinary embedding $H_{1}$ and its target $H_{2}$ . By the copy-embedding equivalence, $H_{2}$ contains no copy of $H_{1}$ . Relabelling preserves the equal-order hypothesis.

Source notes

The cited article uses this orientation in the equal-order case. The argument above derives it from mutual-embedding rigidity; in fact that rigidity gives the orientation even without the equal-order hypothesis.

Depends on

Used by · 1

Join separator for equal-order targets

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. 2, Section 3, ordinary classes, equal-order case