Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫  π  -¹ ² ³ °

You are not logged in.

## #1 2010-10-12 19:58:17

boy15
Member
Registered: 2010-03-29
Posts: 16

### all trees planar?

Hey guys, I am learning about trees and one of the questions from my book what to prove that all trees are bipartite (so they are 2-colorable). I did this fine by induction but the next question says:

Offline

## #2 2010-10-12 21:57:51

boy15
Member
Registered: 2010-03-29
Posts: 16

### Re: all trees planar?

Ok, I might be getting somewhere.

A graph is planar if it can be drawn without edges that intersect within a plane. I believe this is true for all trees, right?

Do I use Euler's formula: v-e+f=2 where for a tree, f=1?

Last edited by boy15 (2010-10-12 22:02:15)

Offline

## #3 2010-10-12 22:23:41

nha
Member
Registered: 2010-09-05
Posts: 43

### Re: all trees planar?

boy15 wrote:

Ok, I might be getting somewhere.

A graph is planar if it can be drawn without edges that intersect within a plane. I believe this is true for all trees, right?

Do I use Euler's formula: v-e+f=2 where for a tree, f=1?

Yes, for a tree, f=1 and remember that for any tree the number of edges is 1 less than the number of vertices, so you have:

v=v, e=v-1 and f=1

so: v-e+f=v-(v-1)+1=2

So all trees are planar.

Offline