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.

Independent deletion decreases beta

PDF p. 3: Section 3, paragraph beginning Observe that

Statement

If $H$ is a finite connected simple graph with an edge, there is an independent set $I \subseteq V (H)$ such that $β (H - I) < β (H)$ .

An independent set contains no two adjacent distinct vertices. The graph $H - I$ is the induced graph on $V (H) ∖ I$ . A block is a maximal 2-connected subgraph or a bridge together with its endpoints; a 2-connected graph has at least three vertices, is connected, and remains connected after deletion of any one vertex, and a bridge is an edge whose deletion increases the number of components. For a nonempty graph with an edge, $β$ is the largest number of vertices in a block; for a nonempty edgeless graph, $β = 1$ .

Facts & Assumptions

[F1]

On a finite connected simple graph with an edge, the block-transversal procedure can be carried out and outputs a vertex set $I$ . Its output is independent and meets every block. Greedy choice in the block-cutvertex tree The greedy set is independent and meets every block

[F2]

If a finite simple graph has an edge and $I$ is independent, then deletion of $I$ leaves a nonempty finite graph. Vertex deletion produces the induced graph on the remaining vertices. Nonempty remainder after deleting an independent set Vertex and edge deletion, edge contraction, graph minors, subdivisions and topological minors

[F3]

If a set $S$ meets every nontrivial block of a finite connected simple graph $J$ with an edge and $J - S$ is nonempty, then $b (J - S) < b (J)$ , where $b$ is the largest nontrivial-block order for a graph with an edge and is $1$ for a nonempty edgeless graph. Block-hitting deletion lowers maximum block order

[F4]

The blocks in the statement are exactly the nontrivial blocks defining $b$ , and $β = b$ on every nonempty finite simple graph under these conventions. Independence has the meaning stated above. Blocks and the parameter beta Cutvertices, 2-connected pieces and nontrivial blocks Order, size, complement and independence number

Proof

Given: A finite connected simple graph $H$ with an edge.

Goal: Find an independent $I \subseteq V (H)$ with $β (H - I) < β (H)$ .

1.1F1given

Run the block-transversal procedure on $H$ and take its output $I$ . The hypotheses permit the procedure, and its output is independent and meets every block of $H$ .

2.1F2F3F4step 1.1

Since $H$ has an edge and $I$ is independent, $H - I$ is nonempty and finite. The blocks met by $I$ are exactly the nontrivial blocks used in the definition of $b$ . Applying the block-hitting deletion result to $H$ and $I$ gives $b (H - I) < b (H)$ .

3.1F2F4step 1.1step 2.1∎

Both $H$ and $H - I$ are nonempty finite simple graphs, so $β = b$ for each. Thus $β (H - I) < β (H)$ , and the independent set $I$ has the required properties.

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.

Sources

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