
- Discrete Mathematics - Home
- Discrete Mathematics Introduction
- Mathematical Statements and Operations
- Atomic and Molecular Statements
- Implications
- Predicates and Quantifiers
- Sets
- Sets and Notations
- Relations
- Operations on Sets
- Venn Diagrams on Sets
- Functions
- Surjection and Bijection Functions
- Image and Inverse-Image
- Mathematical Logic
- Propositional Logic
- Logical Equivalence
- Deductions
- Predicate Logic
- Proof by Contrapositive
- Proof by Contradiction
- Proof by Cases
- Rules of Inference
- Group Theory
- Operators & Postulates
- Group Theory
- Algebric Structure for Groups
- Abelian Group
- Semi Group
- Monoid
- Rings and Subring
- Properties of Rings
- Integral Domain
- Fields
- Counting & Probability
- Counting Theory
- Combinatorics
- Additive and Multiplicative Principles
- Counting with Sets
- Inclusion and Exclusion
- Bit Strings
- Lattice Path
- Binomial Coefficients
- Pascal's Triangle
- Permutations and Combinations
- Pigeonhole Principle
- Probability Theory
- Probability
- Sample Space, Outcomes, Events
- Conditional Probability and Independence
- Random Variables in Probability Theory
- Distribution Functions in Probability Theory
- Variance and Standard Deviation
- Mathematical & Recurrence
- Mathematical Induction
- Formalizing Proofs for Mathematical Induction
- Strong and Weak Induction
- Recurrence Relation
- Linear Recurrence Relations
- Non-Homogeneous Recurrence Relations
- Solving Recurrence Relations
- Master's Theorem
- Generating Functions
- Graph Theory
- Graph & Graph Models
- More on Graphs
- Planar Graphs
- Non-Planar Graphs
- Polyhedra
- Introduction to Trees
- Properties of Trees
- Rooted and Unrooted Trees
- Spanning Trees
- Graph Coloring
- Coloring Theory in General
- Coloring Edges
- Euler Paths and Circuits
- Hamiltonion Path
- Boolean Algebra
- Boolean Expressions & Functions
- Simplification of Boolean Functions
- Advanced Topics
- Number Theory
- Divisibility
- Remainder Classes
- Properties of Congruence
- Solving Linear Diophantine Equation
- Useful Resources
- Quick Guide
- Useful Resources
- Discussion
Planar Graphs in Discrete Mathematics
Graph theory is a part of discrete mathematics, where we see different types of graphs in action. Planar graphs are a special type of graph. They are special because they can be drawn in a two dimensional plane without any edges crossing.
In this chapter, we will see the basics of planar graphs with easy-to-understand examples along with the explanations of core concepts like Eulers formula and non-planar graphs.
What is a Planar Graph?
A planar graph is a special type of graph that can be drawn on a flat plane. No two edges intersect except at their endpoints (vertices). When a graph is drawn this way, it divides the plane into distinct regions known as faces.

Here we have 4 vertices and they have no intersecting edges so it is a planer graph.
Drawing Planar Graphs
For a graph to be planar, we must draw it in a way that it prevents edges from crossing each other. So, sometimes a graph may look non-planar initially, but with careful redrawing, it can be made planar.
Let us understand this concept with a simple example. Take a look at the following graph.

It is a graph with 5 vertices and 6 edges. It is not a planar graph because it has two edges AD and BC which are intersecting each other.
Let's now draw the same graph in a different way; like the one shown below −

Observe that it is the same graph but its vertex D is now placed outside and it has now transformed into a planer graph.
Let us now take a look at a non-planar graph −

Wherever we might try to place the vertex E, it will never become a planar graph.
Faces in Planar Graphs
A planar graph can be successfully drawn without any crossing edges. The edges and vertices naturally split the plane into regions, or faces. As we know, one of these regions will always be the "outside" of the graph, forming a boundary that encircles everything else.

Eulers Formula: A Key Concept in Planar Graphs
When we are talking about planar graphs, we must follow the Eulers formula. This is much useful to relate the vertices, edges, and faces of any connected planar graph.
For any planar graph, the Eulers formula states −
$$\mathrm{v \:-\: e \:+\: f \:=\: 2}$$
where −
- v is the number of vertices,
- e is the number of edges,
- f is the number of faces.
Applying Eulers Formula
Consider the previous example with faces. We have 5 vertices, 6 edges and 3 faces. If we plug them into the formula, it will become −
$$\mathrm{5 \:-\: 6 \:+\: 3 \:=\: 2}$$
This verifies that Eulers formula holds. For any connected planar graph, whether simple or complex, the values of vertices, edges, and faces will satisfy this equation.
The Eulers formula is true regardless of the arrangement of vertices or edges for a connected planar graph. Even if we add extra vertices and edges, as long as the graph can be redrawn without any edge intersections, it will continue to satisfy the Eulers formula.
What are Non-Planar Graphs?
If a graph cannot be drawn on a plane, it belongs to the category of non-planar graphs. When there are too many edges for the number of vertices, it becomes impossible to draw the graph without intersecting edges.
A complex example like complete graphs K5 (with 5 vertices) and the complete bipartite graph K3,3 are classic examples of non-planar graphs.
Example of Non-Planar Graphs
The graph K5 has 5 vertices connected to every other vertex. It has 10 edges. Euler's formula and additional conditions for planarity show that K5 cannot be drawn without edges crossing. Similarly, the bipartite graph K3,3 consists of two sets of three vertices.
Every vertex from one set is connected to every vertex in the other. This setup is mathematically impossible to achieve on a plane without intersections.

Applications of Planar Graphs: Polyhedra and Beyond
Planar graphs have a large variety of applications, particularly in geometry. For instance, they can be used to represent polyhedral. This is a three-dimensional solids with flat faces and straight edges.
When a polyhedron like a cube is projected onto a plane, it forms a planar graph. Here the vertices and edges of a cube satisfy Eulers formula. It has eight vertices, twelve edges, and six faces. We will see Polyhedra in detail in the next chapter.
Regular Polyhedra: The Five Platonic Solids
The concept of polyhedra using planar graphs can be extended to the five regular polyhedral. They are also known as the Platonic solids. These solids are special because each face is an identical polygon. Every vertex connects the same number of edges.
The five regular polyhedra are −
- Tetrahedron
- Cube
- Octahedron
- Dodecahedron
- Icosahedron
Theorems and Proofs in Planar Graph Theory
Let us see some special proofs based on planar graphs.
Proving Non-Planarity: A Look at K5 and K3,3
Proofs for the non-planarity of graphs like K5 and K3,3 often rely on logical contradiction. We may think of that the graph is planar, we can apply Euler’s formula, and find that certain required conditions cannot be met.
For instance, with K5, if we assume planarity, we find that the number of edges surrounding the faces creates an impossible situation. This is proving that no planar representation exists.
Girth and Boundaries in Planar Graphs
In more complex cases, the concept of girth (the length of the shortest cycle in a graph) helps determine whether a graph is planar. By analyzing the boundaries surrounding the faces, one can establish whether a planar arrangement is impossible. If specific girth and boundary conditions are not met, the graph cannot be planar.
Conclusion
In this chapter, we explained the concept of planar graphs. Starting with the basic definition and moving through fundamental concepts such as faces, we covered the Euler's formula and its applications in geometry. We also touched upon non-planar graphs to provide a clear understanding of why certain graphs cannot avoid edge intersections.
We covered how planar graphs relate to polyhedra and discovered how the properties of regular polyhedra like the Platonic solids reflect the principles of planar graph theory.