Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-generatedSession-authored (Fable 5 assisted)precheck passaudited 2026-08-28
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.

Every nontrivial P4-free graph is disconnected or has disconnected complement

Statement

Let G be a finite simple graph with at least two vertices. If G is P4-free, then G is disconnected or G is disconnected. Equivalently, no nontrivial P4-free graph is both connected and anticonnected.

Facts & Assumptions

Given: A finite simple graph G with V(G)2 that is P4-free.

[L1]

Every finite graph with at least two vertices is connected or anticonnected (Every graph with at least two vertices is connected or anticonnected).

[L2]

A graph is anticonnected exactly when its complement is connected (Anticonnected graphs and anticonnected components).

[F1]

In a connected graph every vertex has a neighbour, and if G is connected then no vertex of G is adjacent to all other vertices (Connected graphs and connected components defined by the existence of vertex paths, Graph isomorphisms, automorphisms and graph complements).

Proof

technique · direct
1.1

By [L1], if G is disconnected then the first alternative of the Statement already holds. Assume instead that G is connected.

L1given
1.2

Suppose for contradiction that G is also anticonnected. Then [L2] makes G connected. Choose a vertex vV(G). Because G is connected and nontrivial, [F1] gives a neighbour x of v. Because G is connected, [F1] also gives a vertex y nonadjacent to v. Among all pairs (a,b) with vaE(G) and vbE(G), choose one for which the distance from a to b in G is minimal. Let a=u0,u1,,um=b be a shortest a-b path in G.

step 1.1L2F1chooseassume-contra
2.1

Since a and b are nonadjacent, one has m2. A shortest path is induced, so u0u2E(G) and no nonconsecutive pair among u0,u1,,um is adjacent. If some ui with 1i<m were adjacent to v, then (ui,b) would be another neighbour/nonneighbour pair for v whose distance is mi<m, contradicting the choice in step 1.2. Hence vu1,vu2E(G).

step 1.2algebra
3.1

The four vertices v,u0,u1,u2 therefore induce a path: the edges are vu0, u0u1, and u1u2, while the nonedges are vu1, vu2, and u0u2. This is an induced copy of P4, contradicting [L3].

step 2.1L3discharge-contradiction
4.1

So a nontrivial P4-free graph cannot be both connected and anticonnected. Since step 1.1 reduced to the connected case, [L2] shows that whenever G is connected, G must be disconnected.

step 1.1step 3.1L2

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