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 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 K_3,3 or K₅. 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 K_3,3 and K₅ contain cycles. A tree contains no cycles. Therefore, it is impossible for any subgraph of a tree to be homeomorphic to K_3,3 or K₅. 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.

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. A tree with one vertex is planar. The statement is true for n = 1.

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 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.

References
Euler’s Graph