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

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**mrpace****Member**- Registered: 2012-08-16
- Posts: 73

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

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'

I'm not crazy, my mother had me tested.

Offline

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'

I'm not crazy, my mother had me tested.

Offline

Pages: **1**