Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2013-05-28 11:30:32

mrpace
Member
Registered: 2012-08-16
Posts: 54

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?

Offline

#2 2013-05-28 14:54:47

Agnishom
Real Member
From: The Complex Plane
Registered: 2011-01-29
Posts: 18,872
Website

Re: question on graph theory?

It is exactly

Last edited by Agnishom (2013-05-28 15: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'
'You have made another human being happy. There is no greater accomplishment.' -bobbym

Offline

#3 2013-05-28 16:10:45

Agnishom
Real Member
From: The Complex Plane
Registered: 2011-01-29
Posts: 18,872
Website

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 K[sub]2[/sub]

So let us start with the base case of K[sub]2[/sub]
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, m[sub]new[/sub] = m[sub]old[/sub] + 1
and n[sub]new[/sub] = n[sub]old[/sub] + 1

Therefore,  m[sub]new[/sub] = m[sub]old[/sub] + 1 =  (n[sub]old[/sub] - 2) + 1 = (n[sub]old[/sub] + 1) - 2 = n[sub]new[/sub] - 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'
'You have made another human being happy. There is no greater accomplishment.' -bobbym

Offline

Board footer

Powered by FluxBB