# Prove 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,