Alphabeta Math
ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck 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.

The five-cycle is 2-narrow but not 1-narrow

Example

The cycle graph C5 is two-narrow but not one-narrow.

Facts & Assumptions

Given: The cycle graph C5.

[L1]

If every vertex deletion of a graph with at least three vertices is perfect, then the graph is two-narrow (Perfect vertex deletions imply 2-narrowness).

[L2]

The graph C5 is not perfect (The five-cycle is bull-free but not perfect).

[F1]

A graph is one-narrow when every good function has total weight at most 1 (An α-narrow graph).

[F2]

A good function is a nonnegative weighting whose total on every perfect induced subgraph is at most 1 (A good function on a graph).

[F3]

The graph C5 is the five-vertex cycle (Empty and complete graphs, complete bipartite graphs, and the convention that Pn and Cn have n vertices). A graph is perfect when each of its induced subgraphs has chromatic number equal to clique number (A perfect graph).

Verification

technique · direct
1.1F3L1

Deleting any vertex of C5 leaves a four-vertex path. Every induced subgraph of that path is a disjoint union of paths. If it has an edge, alternating colours on each path give chromatic number at most 2, and the edge gives clique number at least 2, so both numbers are 2; if it is nonempty and has no edge, both are 1; and if it is empty, both are 0. Thus every vertex deletion is perfect by [F3]. Since C5 has five vertices, [L1] proves that C5 is two-narrow.

2.1step 1.1L2F1F2algebra

Define g(v)=1/4 for every vertex of C5. Every proper induced subgraph lies in some vertex deletion, so it is perfect by step 1.1. Since [L2] says the whole C5 is not perfect, every perfect induced subgraph is proper and has at most four vertices. Thus [F2] makes g a good function: its total on each perfect induced subgraph is at most 4⋅(1/4)=1. But ∑v∈V(C5)g(v)=5/4>1, so [F1] shows that C5 is not one-narrow.

3.1step 1.1step 2.1∎

Thus C5 is two-narrow by step 1.1 but not one-narrow by step 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