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

Login

Username

Password

Not registered yet?

Post a reply

Go back

Write your message and submit
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool: | :dizzy :eek :kiss :roflol :rolleyes :shame :down :up :touched :sleep :wave :swear :tongue :what :faint :dunno
Options

Go back

Topic review (newest first)

Agnishom
2013-05-29 14:10:45

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

Agnishom
2013-05-29 12:54:47

It is exactly

mrpace
2013-05-29 09:30:32

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?

Board footer

Powered by FluxBB