A certain tree T of order n has only vertices of degree 1 and 3. Show that T contains (n-2)/2 vertices of degree 3.
Well I know it will have n-1 edges.
I also know by the first theorem of graph theory
that
sum (deg vertices)=2(size)=2(n-1)
I can let x=number of vertices of degree 1 and n-x=number of degree 3.
So
x+(n-x)=2(n-1), but then I get confused because the x's cancel and I have
n=2n-2
Or
n-2=0
n=2...That doesn't make sense though...what is wrong?
Nevermind, I got it...I forgot it was 3x


LinkBack URL
About LinkBacks