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

Login

Username

Password

Not registered yet?

#1 2013-05-29 09:30:32

mrpace
Member

Offline

question on graph theory?

Every vertex of a certain tree has degree 1 or 3. If n vertices have degree 1, how
many have degree 3?

how can i show this?

#2 2013-05-29 12:54:47

Agnishom
Real Member
Award: Wink Sherlock

Online

Re: question on graph theory?

It is exactly

Last edited by Agnishom (2013-05-29 13:35:59)


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'Who are you to judge everything?' -Alokananda

#3 2013-05-29 14:10:45

Agnishom
Real Member
Award: Wink Sherlock

Online

Re: question on graph theory?

Disclaimer: I am not sure about how things about graphs are proved but this is a outline

Proof

Since, A tree Graph is connected it must be a supergraph of K2

So let us start with the base case of K2
Here, the number of leaves are 2 and the number of internal vertex are 0
So m(number of internal vertices) = n(number of leaves) - 2 in this case

Now, every time we make a supergraph of it such that the property of the tree is preserved: We add 2 vertices connected to one of the leaves.

Now, the number of internal vertices is increased by one (since the old leaf has now two vertices connected to it).
We have two new leaves, but one previous leaf is now an internal vertex. So, the number of leaves has also increased by one.

So, mnew = mold + 1
and nnew = nold + 1

Therefore,  mnew = mold + 1 =  (nold - 2) + 1 = (nold + 1) - 2 = nnew - 2

Thus, by induction the number of vertices that have degree 3 is equal to (n-2) always in such a tree


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'Who are you to judge everything?' -Alokananda

Board footer

Powered by FluxBB