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,
As we can see in the figure, the new vertex will just add a new branch to the tree. Adding a new branch will not affect the planarity of the tree.
Therefore, n = k + 1 is planar.
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