Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passverified 2026-09-24 (gpt-6-sol)
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.

Substituting two α-narrow graphs yields another α-narrow graph

Statement

Let α>0. If H1 and H2 are α-narrow finite graphs and the substitution G=H1[v→H2] is defined, then G is α-narrow.

Facts & Assumptions

Given: A real number α>0, α-narrow finite graphs H1 and H2, and a defined substitution G=H1[v→H2].

[F1]

A graph is α-narrow when every good function has α-power sum at most 1 (An α-narrow graph).

[F2]

In a substitution, every vertex of the substituted graph H2 has exactly the outside adjacencies that the vertex v had in H1 (Substituting one graph for a vertex of another).

[L1]

Substituting a perfect graph for a vertex of a perfect graph preserves perfection (Substituting a perfect graph into a perfect graph preserves perfection).

Proof

technique · direct
1.1F1F2choosealgebra

Let g be a good function on G. Let P2 be the family of perfect induced subgraphs of H2, and let K=max⁡P∈P2∑x∈V(P)g(x). If K=0, then every one-vertex induced subgraph of H2 has weight 0, so g vanishes on V(H2). Choose any vertex x∈V(H2), define g1 on H1 by copying g outside v and setting g1(v)=0, and note from [F2] that every perfect induced subgraph of H1 corresponds either to the same perfect induced subgraph of G or to one obtained by replacing v with x. Hence g1 is good on H1, so [F1] gives ∑y∈V(H1)g1(y)α≤1. Because g vanishes on H2, this is exactly ∑z∈V(G)g(z)α≤1.

1.2F1L1choosealgebra

Assume now that K>0. Define g1 on H1 by copying g outside v and setting g1(v)=K. If Q is a perfect induced subgraph of H1 not containing v, then it appears unchanged in G and has total g1-weight at most 1. If v∈V(Q), choose P∈P2 with ∑x∈V(P)g(x)=K; then [L1] makes the substitution Q[v→P] a perfect induced subgraph of G, so ∑y∈V(Q)g1(y)=∑y∈V(Q)∖{v}g(y)+K=∑z∈V(Q[v→P])g(z)≤1. Thus g1 is good on H1. Likewise g2:=g/K is good on H2 by the definition of K. Applying [F1] to g1 and g2 gives ∑y∈V(H1)∖{v}g(y)α+Kα≤1 and ∑x∈V(H2)g(x)α≤Kα.

2.1step 1.1step 1.2F1∎

In the case K>0, step 1.2 yields ∑z∈V(G)g(z)α=∑y∈V(H1)∖{v}g(y)α+∑x∈V(H2)g(x)α≤1. Together with step 1.1, this proves that every good function on G has α-power sum at most 1. Therefore [F1] shows that G is α-narrow.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

13 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