Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: √ ∞ ≠ ≤ ≥ ≈ ⇒ ∈ Δ θ ∴ ∑ ∫ π -

Login

Username

Password

Not registered yet?

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

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

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

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

Board footer

Powered by FluxBB