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

You are not logged in.

## #1 2010-10-13 18:58:17

boy15
Member

Offline

### 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:

## #2 2010-10-13 20:57:51

boy15
Member

Offline

### 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-13 21:02:15)

## #3 2010-10-13 21:23:41

nha
Member

Offline

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