Alphabeta Math
TheoremStatement: AI-adaptedProof: AI-generatedprecheck 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 ∅≠S⊊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⊊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 ∣A∣ 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

Dependency tree · two levels

16 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources