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

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

Statement

Let $G$ be a simple planar graph with $n \geq 3$ vertices. If $G$ has exactly $3 n - 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 $3 n - 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 \geq 3$ vertices and $m$ edges satisfies $m \leq 3 n - 6$ . Every plane triangulation with at least three vertices has equality (Every simple planar graph with $n \geq 3$ vertices has at most $3 n - 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) ∣ = 3 n - 6$ .

L1L2

2.1

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

step 1.1L1

3.1

Step 2.1 holds for every $n \geq 3$ , 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 · two levels

19 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

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−6 edges