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 Kuratowski’s Theorem
According to Kuratowski’s Theorem, a graph is non-planar if and only if one of its sub-graphs is homeomorphic to K3,3 or K5. A Graph G1 is homeomorphic to Graph G2 if we can convert G1 to G2 by sub-division or smoothing.
Sub-division: Suppose an edge (v,u). Sub-division means removing edge (v,u) and adding a vertex w and two new edges (v,w) and (w,u).
Smoothing: Suppose edges (v,w) and (w,u) such that degree of w is 2. Smoothing means removing vertex w and adding a new edge (v,u).
Now, both K3,3 and K5 contain cycles. A tree contains no cycles. Therefore, it is impossible for any subgraph of a tree to be homeomorphic to K3,3 or K5. Thus, 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 in the tree.
First, we will prove that the statement is true for n = 1.
n = 1 means a tree with only 1 vertex and no edges. A tree with one vertex is planar. The statement is true for n = 1.
In this step, we will assume that a tree, n = k is planar.
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 proved that n = k + 1 is planar if n = k is planar. Therefore, we can say that the statement “every tree is planar” is true for all n >= 1.