351 views
1 votes
1 votes
if t is a complete n tree with exactly three level ,prove that the no. of vertices of t must be 1+kn,where 2<=k<=n+1

1 Answer

1 votes
1 votes
Let k be the number of non-leaves.

By the definition of n-tree, the non-leaves must have n child, so there are child of these k non-leaves.

For every vertex (except the root) is the children of some non-leaf and the root is not the child of any vertex, then there are vertices in T.

Since T has 3 levels, then there must be at least 2 non-leaves: the root and at least one of its children that is non-leaf.

Moreover, there are at most n+1 non-leaves: the root and all its children that are non-leaves.

Hence,  2 ≤ k ≤ n+1.

Related questions

1 votes
1 votes
1 answer
1
0 votes
0 votes
1 answer
2
gagan55 asked Jun 30, 2023
177 views
Number of hamiltonian cycles for a graph K 5, 5( bipartite graph ) ??
0 votes
0 votes
1 answer
3
Dhiraj_777 asked May 4, 2023
488 views
In a Connected Planar Bipartite Graph of order 10 atmost how many edges be present ?
0 votes
0 votes
1 answer
4
Sahil_Lather asked Apr 15, 2023
439 views
Graph G is obtained by adding vertex s to $K_{3,4}$ and making s adjacent to every vertex of $K_{3,4}$ .The find the minimum number of colours required ot edge-colour is ...