TheoremStatement: AI-adaptedProof: AI-generatedSession-authored (Fable 5 assisted)precheck passaudited 2026-08-02

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.

If $G$ has a Hamilton cycle, then deleting any nonempty proper vertex set $S$ leaves at most $|S|$ connected components

Statement

If a finite simple graph $G$ has a Hamilton cycle and $\varnothing\ne S\subsetneq V(G)$ , then the vertex-deleted graph $G-S$ has at most $|S|$ connected components.

Facts & Assumptions

Given: A Hamilton cycle $C$ of $G$ and a nonempty proper set $S\subsetneq V(G)$ .

[F1]

The cycle $C$ contains every vertex of $G$ exactly once before returning to its initial vertex (Hamilton paths, Hamilton cycles, Hamiltonian graphs and Hamilton-connected graphs).

[F2]

Vertex deletion removes $S$ and all incident edges (Vertex and edge deletion, edge contraction, graph minors, subdivisions and topological minors).

[F3]

Connected components are maximal vertex sets joined by paths (Connected graphs and connected components defined by the existence of vertex paths).

[F4]

The finite cardinality $|S|$ counts the vertices of $S$ (The cardinality $\lvert A\rvert$ of a finite set).

Proof

technique · direct

1.1

Deleting the vertices of $S$ from the cyclic order of $C$ leaves one or more vertex-disjoint path segments containing every vertex of $G-S$ . Each such segment is preceded around $C$ by a distinct vertex of $S$ , so the number of segments is at most $|S|$ .

givenF1F2F4

2.1

Every path segment from step 1.1 remains a path in $G-S$ . Adding the other edges of $G-S$ can merge such segments into a connected component but cannot split one, so $G-S$ has no more components than those segments.

step 1.1F2F3

3.1

Therefore the number of connected components of $G-S$ is at most $|S|$ .

step 1.1step 2.1∎

Depends on

Used by

Every Hamiltonian graph on at least three vertices is 2-connected Corollary
P₃ has a Hamilton path but no Hamilton cycle Counterexample
Two triangles sharing one vertex form an Eulerian graph with no Hamilton cycle Counterexample

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 33 results over 17 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.

Sources

Applied Combinatorics, Eulerian and Hamiltonian Graphs (standard reference, not scraped)

If GGG has a Hamilton cycle, then deleting any nonempty proper vertex set SSS leaves at most ∣S∣|S|∣S∣ connected components