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

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.

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.

Common mistakes: diagnose the condition first
Mistake | Why it happens | What goes wrong | Repair |
|---|---|---|---|
Omitting the outer face | Only bounded regions stand out |
| Count the unbounded region |
Using the connected formula on |
| It gives | Use |
Treating a crossing as a vertex | The picture replaces the definition |
| Find a plane embedding first |
Counting a bridge once | Both sides touch one face | The sum falls below | Count both boundary traversals |
Assuming a new embedding changes total | Faces look different | Shape is confused with invariance | Use |
Applying | Simplicity is missed | The derivation fails | Confirm the graph is simple |
Using | 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 |
| Choose the strongest justified filter |
Exam-style workflow and two timed calculations
Use this six-step checklist:
Confirm that a crossing-free embedding is given or may be assumed.
Count the components
C.Count
VandEwithout double-counting.Include the outer face.
Check whether simple, triangular-faced, triangle-free, or bipartite conditions justify a bound.
Compute, then reverse-check with Euler and
sum deg(face) = 2Ewhere 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.Ccomponents: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.
Keep learning
Euler Formula for Planar Graphs MCQs: 12 Solved Applications and Derived Relations
Solve 12 Euler Formula MCQs step by step, from direct substitution and bounded faces to degree sums, components and careful planarity screening.
Planar Graphs and Euler's Formula for GATE: Planarity Checks, Matching and Vertex Covers Solved
Use Euler's formula and the correct planar edge bound on K4, K5 and K3,3. Then connect maximum matching to minimum vertex cover in a solved bipartite graph.
Planar Graphs MCQs: 12 Solved Questions on Kuratowski’s Theorem, Homeomorphism and Edge Bounds
Solve 12 planar graph questions, then check each answer through a forbidden-subdivision argument, a crossing-free redraw, or a short calculation.
Graph Coloring: Vertex Coloring, Edge Coloring, Chromatic Number and Theorem Bounds
Learn to separate vertex coloring from edge coloring, prove exact chromatic values on one six-vertex graph, and apply standard theorem bounds without overclaiming.





