CorollaryStatement: Literature-sourcedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck passaudited 2026-08-11

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 simple planar graph with $n\ge3$ vertices has at most $2n-4$ edges

Statement

Every triangle-free simple planar graph with $n\ge3$ vertices and $m$ edges satisfies $m\le2n-4$ . Triangles and cycles have the convention of Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges.

Facts & Assumptions

Given: A triangle-free simple planar graph with a fixed embedding and $n\ge3$ .

[L1]

For every connected plane graph, $|V|-|E|+|F|=2$ (Euler's formula $|V|-|E|+|F|=2$ for every connected plane graph).

[L2]

For a connected plane graph, if every facial boundary walk has length at least $g$ , then $g|F|\le2|E|$ (Facial boundary walks of a connected plane graph sum to $2|E|$ , and if every such walk has length at least $g$ then $g|F|\le2|E|$ ).

Proof

technique · direct

1.1

Suppose first the graph is connected. If it is a tree, $m=n-1\le2n-4$ . Otherwise every facial boundary walk has length at least four: lengths one and two are excluded by simplicity except for a lone bridge component, and length three would be a triangle.

given

2.1

In the non-tree case, [L2] with $g=4$ and [L1] give $4(2-n+m)\le2m$ , hence $m\le2n-4$ . Together with the tree case this proves the connected bound.

step 1.1L1L2algebra

3.1

For a disconnected graph, first redraw it: each component drawing is bounded, so translating and scaling the components into pairwise disjoint discs puts every component on the unbounded face without changing the abstract graph, on which the bound depends. Now join the components through that face by noncrossing bridge edges. No cycle, and hence no triangle, is added; the connected augmented graph has the same $n$ and at least as many edges. Step 2.1 gives the required bound for the original graph.

step 2.1construct∎

Depends on

Used by

K₅ and K_3,3 are nonplanar Corollary

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 46 results over 13 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.

Sources

R. Diestel, Graph Theory, 6th ed., Chapter 4, Section 4.2 (standard reference, not scraped)
R. Grassl and O. Levin, Exploring Combinatorial Mathematics, Activity 296 (standard reference, not scraped)

Every triangle-free simple planar graph with n≥3n\ge3n≥3 vertices has at most 2n−42n-42n−4 edges