False statementConstruction: AI-adaptedVerification: AI-adaptedprecheck passaudited 2026-08-13

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 triangle-free graph is bipartite

False Statement

Every triangle-free graph is bipartite.

Facts & Assumptions

Given: The hypotheses and notation of the statement above.

[F1]

For $n \geq 3$ , $C_{n}$ has the consecutive edges ${i, i + 1}$ and the closing edge ${n - 1, 0}$ (Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

[F2]

A finite simple graph is bipartite if and only if it contains no odd cycle (A finite graph is bipartite if and only if it has no odd cycle).

Refutation

technique · give the five-cycle

1.1givenF1

The only cycle in $C_{5}$ using three edges would require a chord, and $C_{5}$ has only its five consecutive edges. Hence $C_{5}$ is triangle-free.

1.2givenF2

The graph $C_{5}$ is itself an odd cycle, so the cited equivalence says it is not bipartite.

2.1step 1.1step 1.2∎

Thus $C_{5}$ satisfies the premise and fails the conclusion, refuting the statement.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

11 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

Yufei Zhao, Graph Theory and Additive Combinatorics (standard reference, not scraped)