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_{5}**. 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

_{5}**K**. Thus, we can say that every tree is planar.

_{3,3 }or K_{5}### 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,

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

**References**

Euler’s Graph

anonYour proof using Euler’s formula is incorrect. Euler’s formula only works for planar graphs, it can be used to proof that a graph is not planar, but not that one is planar.

adminI updated it.

Thanks.