Euler Formula for Planar Graphs: Face Counts, Edge Bounds, and Non-Planarity Tests

Learn how to count faces correctly, extend Euler's relation to disconnected plane graphs, derive edge bounds, and use those bounds without reversing their logic.

KnowledgeGate Team

Exam prep & CS education

Updated 1 Nov 20266 min read
Euler Formula for Planar Graphs: Face Counts, Edge Bounds, and Non-Planarity Tests

The arithmetic in Euler's formula is easy, but answers fail when a graph has several components, the outer face is omitted, a bridge is counted on only one side, or an edge bound is used without checking its conditions. Reliable Euler-formula calculations require a labelled embedding, complete face counts, the disconnected form, derived bounds, non-planarity tests, and a compact solving workflow.

Euler formula starts with the right objects

A planar graph has at least one crossing-free drawing. A plane graph is one fixed crossing-free embedding. Faces belong to the embedding, and F includes the unbounded outer face.

For a connected plane graph,

V - E + F = 2.

Do not feed a drawing with crossings into this formula. A geometric crossing is not a vertex unless the graph declares it. First find a plane embedding, then count V, E, and F.

For graph vocabulary, see Graph Theory: Euler, Hamiltonian, Coloring for GATE CS.

Worked example: count every face in the cube graph

Draw outer cycle A-B-C-D-A, inner cycle E-F-G-H-E, and connectors A-E, B-F, C-G, and D-H. This gives V = 8 and E = 4 + 4 + 4 = 12.

The faces are the inner face f1 = E-F-G-H; side faces f2 = A-B-F-E, f3 = B-C-G-F, f4 = C-D-H-G, and f5 = D-A-E-H; and outer face f6 = A-B-C-D. Therefore,

F = 2 - V + E = 2 - 8 + 12 = 6.

Check 8 - 12 + 6 = 2. Each face boundary has length 4, so 6 x 4 = 24 = 2E. Every edge supplies two sides to face-boundary walks, even when both sides border one face.

Cube graph drawn without crossings with its six labelled faces f1 to f6 and the counts V=8, E=12, F=6 giving 8-12+6=2.

Euler formula with components, trees, and bridges

For a plane graph with C connected components, the general form is

V - E + F = 1 + C.

All components share one unbounded face. Take square a-b-c-d-a with diagonal a-c, where V1 = 4 and E1 = 5, plus hexagon p-q-r-s-t-u-p, where V2 = 6 and E2 = 6. Thus V = 10, E = 11, and C = 2:

10 - 11 + F = 1 + 2, so F = 4.

Separately they have three and two faces. Combining their outer regions gives 3 + 2 - 1 = 4.

A tree with V = 6 has E = 5, all bridges. Euler gives F = 2 - 6 + 5 = 1, only the outer face. Each bridge is traversed twice on its boundary walk, so its degree is 2 x 5 = 10 = 2E. A bridge need not separate distinct faces.

Derived edge bounds and triangulations

For a simple connected plane graph with V >= 3, every face boundary has length at least 3, so 3F <= 2E. Substitute F = 2 - V + E:

3(2 - V + E) <= 2E, hence E <= 3V - 6.

Euler then gives F <= 2V - 4. Equality occurs when every face is triangular. At V = 12, such a graph has E = 3(12) - 6 = 30 and F = 2(12) - 4 = 20. Check 12 - 30 + 20 = 2 and 3F = 60 = 2E.

If a simple connected planar graph with V >= 3 is triangle-free or bipartite, each face boundary has length at least 4. Thus 4F <= 2E gives E <= 2V - 4. At V = 10, the maximum is 16, so 17 edges prove non-planarity.

The general bound gives average degree 2E/V <= 6 - 12/V < 6. Thus at least one vertex has degree at most 5.

Applications: prove non-planarity without redrawing

The face-length method extends beyond lengths 3 and 4. If every face boundary in a simple connected plane graph has length at least g >= 3, then gF <= 2E. Combining this with Euler's formula gives E <= g(V - 2)/(g - 2). At g = 5 and V = 12, the bound is E <= 50/3, hence E <= 16 for an integer edge count. A graph with E = 21 and the stated face-boundary condition is therefore non-planar. The familiar K5 check is the g = 3 case: E = 10 > 3V - 6 = 9.

K3,3 shows why the stronger condition matters. It has V = 6 and E = 9, so it passes the loose check 9 <= 3(6) - 6 = 12. But it is bipartite and triangle-free. A planar embedding would require E <= 2(6) - 4 = 8; 9 > 8, so K3,3 is non-planar.

These inequalities are the Euler-derived arithmetic screen. Planar Graphs and Kuratowski's Theorem takes over when a bound passes, using subdivisions and degree-two suppression to expose a structural obstruction.

Violating an applicable bound proves non-planarity, but satisfying it does not prove planarity. Do not apply these bounds unchanged to multigraphs. Loops and parallel edges break the simple-graph face-length premise.

K5 and K3,3 side by side with their counts: K5 has E=10 above the bound 3V-6=9, and K3,3 has E=9 above the bipartite bound 2V-4=8.

Common mistakes: diagnose the condition first

Mistake

Why it happens

What goes wrong

Repair

Omitting the outer face

Only bounded regions stand out

F is one too small

Count the unbounded region

Using the connected formula on V=10, E=11, C=2

C is ignored

It gives F=3, not 4

Use V-E+F=1+C

Treating a crossing as a vertex

The picture replaces the definition

V and E change wrongly

Find a plane embedding first

Counting a bridge once

Both sides touch one face

The sum falls below 2E

Count both boundary traversals

Assuming a new embedding changes total F

Faces look different

Shape is confused with invariance

Use F=2-V+E when connected

Applying E<=3V-6 to parallel edges

Simplicity is missed

The derivation fails

Confirm the graph is simple

Using E<=2V-4 because one drawing has no triangle

Appearance replaces a graph property

The bound may not apply

Prove simple, connected, triangle-free or bipartite conditions

Treating a passed bound as proof

Necessary seems sufficient

K3,3 passes the loose bound

Choose the strongest justified filter

Exam-style workflow and two timed calculations

Use this six-step checklist:

  1. Confirm that a crossing-free embedding is given or may be assumed.

  2. Count the components C.

  3. Count V and E without double-counting.

  4. Include the outer face.

  5. Check whether simple, triangular-faced, triangle-free, or bipartite conditions justify a bound.

  6. Compute, then reverse-check with Euler and sum deg(face) = 2E where applicable.

Use GATE CS Exam Preparation to place this method within wider preparation.

A connected simple plane graph has V = 14, and every face boundary is triangular. Euler gives F = E - 12. Combine it with 3F = 2E:

3(E - 12) = 2E, so E = 36 and F = 24.

Verify both ways: 14 - 36 + 24 = 2 and 3 x 24 = 2 x 36 = 72.

A connected plane graph has V = 9 and vertex-degree sum 40. The handshaking lemma gives 2E = 40, so E = 20. Euler gives F = 2 - 9 + 20 = 13. Continue with Graph Theory MCQs: 12 Solved Euler, Coloring, Trees for solved practice on these ideas.

Euler formula: the short version and next step

Keep this revision card:

  • Connected plane graph: V - E + F = 2.

  • C components: V - E + F = 1 + C.

  • Simple planar graph with V >= 3: E <= 3V - 6.

  • Simple triangle-free or bipartite planar graph with V >= 3: E <= 2V - 4.

  • Face-degree sum: sum deg(face) = 2E.

  • The outer face always counts.

Revisit the cube (V,E,F) = (8,12,6), the two-component graph (V,E,C,F) = (10,11,2,4), and the triangulated graph (V,E,F) = (12,30,20). Reproduce each missing value from the proper formula, then explain why K3,3 needs the bipartite bound.

Finally, redraw the labelled cube, recount its faces, and solve the V = 14 triangular-face example without notes. Engineering Mathematics for GATE Exam is the structured course route for placing graph theory within wider mathematics preparation.