You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

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

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.

Offline

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

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

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

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

Pages: **1**