Math Is Fun Forum

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:

"Are all trees therefore planar?" Explain your answer.

I am not sure how to go about this. Any help would be awesome, thanks.

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)

nha

Member

Registered: 2010-09-05

Posts: 43

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?

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.