# Thread: [SOLVED] Graph Theory Question - Vertices

1. ## [SOLVED] Graph Theory Question - Vertices

Hello guys,

I have a question concerning the relationship between vertices in a full binary tree and the internal vertices in a full binary tree. I'm assuming there is a formule for this problem, but I have been unable to locate it.

Thanks for the help, I really need to solve this question:

If a full binary tree has 231 vertices, then it has ____ internal vertices.

Thanks guys and gals!

2. Originally Posted by MathHelp12345
Hello guys,

I have a question concerning the relationship between vertices in a full binary tree and the internal vertices in a full binary tree. I'm assuming there is a formule for this problem, but I have been unable to locate it.

Thanks for the help, I really need to solve this question:

If a full binary tree has 231 vertices, then it has ____ internal vertices.

Thanks guys and gals!
The definition of full binary tree is "a tree in which every node other than the leaves has two children" (Wikipedia). If you draw them on paper, you will notice that you start out with just one vertex, which we can call a leaf, then after that each leaf creates two new leaves while becoming itself an internal vertex. So, each time you add two branches to a leaf, you destroy one leaf and create two more. The overall effect is that the number of leaves is always one greater than the number of internal vertices. So, we could write

n + (n+1) = 231

3. Originally Posted by undefined
The definition of full binary tree is "a tree in which every node other than the leaves has two children" (Wikipedia). If you draw them on paper, you will notice that you start out with just one vertex, which we can call a leaf, then after that each leaf creates two new leaves while becoming itself an internal vertex. So, each time you add two branches to a leaf, you destroy one leaf and create two more. The overall effect is that the number of leaves is always one greater than the number of internal vertices. So, we could write

n + (n+1) = 231

If I'm understanding this correctly the work and answer is as followed:

n vertices has i = (n-1)/m

i = (231-1)/2 => 115.

4. Originally Posted by MathHelp12345

If I'm understanding this correctly the work and answer is as followed:

n vertices has i = (n-1)/m

i = (231-1)/2 => 115.
I think the "m" is supposed to be a 2? Anyway, that's what I get too.

5. Originally Posted by undefined
I think the "m" is supposed to be a 2? Anyway, that's what I get too.
Yep! The 'm' is the m-ary tree, which in this case is 2.