Alphabeta Math
CorollaryStatement: Literature-sourcedProof: AI-adaptedprecheck 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≥3 vertices has at most 2n−4 edges

Statement

Every triangle-free simple planar graph with n≥3 vertices and m edges satisfies m≤2n−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≥3.

[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∣≤2∣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∣≤2∣E∣).

Proof

technique · direct
1.1

Suppose first the graph is connected. If it is a tree, m=n−1≤2n−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)≤2m, hence m≤2n−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

Dependency tree · two levels

17 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