PropositionStatement: 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.

For a two-connected planar graph of order at least three, maximal planarity is equivalent to having $3n-6$ edges

Statement

Let $G$ be a simple planar graph with $n\ge3$ vertices. If $G$ has exactly $3n-6$ edges, then $G$ is maximally planar in the sense of Maximal plane graphs, plane triangulations, and maximally planar abstract graphs. Conversely, if $G$ is two-connected and maximally planar, then $G$ has exactly $3n-6$ edges. The two conditions are therefore equivalent for two-connected $G$ . Two-connectivity is used only through A two-connected plane graph of order at least three is maximal exactly when every face is triangular, which needs a facial boundary to be a cycle; the converse without that hypothesis is not established here.

Facts & Assumptions

Given: Such a planar graph $G$ .

[L1]

Every simple planar graph with $n\ge3$ vertices and $m$ edges satisfies $m\le3n-6$ . Every plane triangulation with at least three vertices has equality (Every simple planar graph with $n\ge3$ vertices has at most $3n-6$ edges, with equality for every plane triangulation).

[L2]

A two-connected plane graph of order at least three is maximal exactly when every face is triangular (A two-connected plane graph of order at least three is maximal exactly when every face is triangular).

Proof

technique · direct

1.1

Let $G$ be two-connected and maximally planar. Every plane embedding of $G$ is maximal plane: otherwise an edge added in that embedding would give a larger planar abstract graph. That embedding is a two-connected plane graph, because two-connectivity is a property of the abstract graph, so [L2] makes it a triangulation and [L1] gives $|E(G)|=3n-6$ .

L1L2

2.1

Conversely, if $|E(G)|=3n-6$ and a missing edge could be added planarly, the resulting simple planar graph on the same $n$ vertices would have $3n-5$ edges, contradicting [L1]. Thus $G$ is maximally planar.

step 1.1L1

3.1

Step 2.1 holds for every $n\ge3$ , and step 1.1 supplies the converse whenever $G$ is two-connected, so the two conditions are equivalent there.

step 1.1step 2.1∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 54 results over 12 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., Proposition 4.4.1 (standard reference, not scraped)

For a two-connected planar graph of order at least three, maximal planarity is equivalent to having 3n−63n-63n−6 edges