Prove every tree is planar

In this article, we will show every tree is planar.

Tree: A tree is a simple connected graph that consists of N – 1 edges where N is the number of vertices. There is exactly one path between any two vertices in a tree. A tree consists of no cycle.

Proof every tree is planar

We can proof it in 2 ways.

Proof By Euler’s Formula

According to Euler’s Formula,

r = e - v + 2
r: number of regions
e: number of edges
v: number of vertices

The number of edges in a tree, e = v – 1

r = (v - 1) - v + 2
r = v - 1 - v + 2
r = 1

From the above, we can say that the number of regions in every tree is 1. A graph with one region is always planar since it shows there are no loops. Thus, no possibility for the intersection of edges.

Therefore, we can say that every tree is planar.

Proof By Induction

We need to prove that a tree is planar for all n >= 1 where n is the number of vertices.

Step 1
First, we will prove that the statement is true for n = 1.
n = 1 means a tree with only 1 vertex and no edges. Thus, n = 1 is the planar.

Step 2
In this step, we will assume that a tree n = k is planar.

Step 3
In this step, we will prove that if n = k is true, then n = k + 1 is also true
We know n = k is planar and consists of k – 1 edge. The tree n = k + 1 consists of k edges. We can convert tree n = k to n = k + 1 by adding a new vertex and connecting it to one vertex in tree n = k. Adding a new vertex and connecting it to one vertex in the tree cannot result in a loop. For example,

We prove that n = k + 1 is planar if n = k is planar. Thus, we can say that the statement every tree is planar is true for all n >= 1.

References
Euler’s Graph